백준 1929번 : 소수 구하기[Java]

문제출처

www.acmicpc.net/problem/1929

1929번: 소수 구하기

3일연속 소수 관련 문제

import java.util.Scanner;
public class d019_Q1929 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int M = sc.nextInt();
		int N = sc.nextInt();
		
		int prime = M;
		while(prime <= N) {
			if(check(prime)) {
				System.out.println(prime);
			}
			prime++;
		}
		sc.close();

	}
	
	public static boolean check(int n) {
		int i = 2;
		if(n == 0 || n == 1) {return false;}
		while(i < n) {
			if(n % i++ == 0) {
				return false;
			}
		}
		return true;
	}

}

 

처음에는 아 또 소수야~ 이러면서 대충 풀었는데 실패. 시간초과였다.

문제에 떡하니 에라토스테네스의 체를 이용해서 풀라고 했는데 맘대로 풀어버렸다.

일단 이게 시간초과인 이유

메인의 while문과 check함수의 while문 두개로 시간이 너무 오래 걸린게 아닐까 하는 생각이 든다.

만약에 M과N이 모두 엄청 큰수에 범위까지 넓다면 check에서 i가 2부터 시작해 큰수인 소수까지 검사할려면 상당히 많이 돌아야 할테니...

 

일단 여기까지 생각하고 더 떠오르지 않아서 질문 게시판을 또 뒤졌다.

상당히 도움이 됐던 글 링크

www.acmicpc.net/board/view/39203

글 읽기 - ★☆★☆★ [필독] 소수 구하기 FAQ ★☆★☆★

지금까지 소수 구하는 방식은 2부터 무식하게 숫자를 계속 나누는 거 밖에 몰랐던 나에게 새로운 지식이 생겼다.

 

첫번째

수의 제곱근 까지만 나누어본다.

 

사실 수학을 재수할때 처음으로 약 6개월만 빡씨게 공부한 야매 이과인간이라 저 글에서 설명하는 제곱근도 제대로 이해를 못해서 수학 용어도 좀 정리하고 가겠다.

제곱근 : 제곱하여 그 수가 되는 수 즉, 4의 제곱근은 2다.

소인수 : 주어진 자연수를 나누어 떨어뜨리는 약수 중에서 소수인 약수

sqrt함수 : Math.sqrt(n)은 n의 제곱근을 반환한다. 반환값은 double형

 

두번째

 

에라토스테네스의 체

 

소수를 판별할 범위 만큼 배열을 할당하여,

해당하는 값을 넣는다.

2부터 특정 수의 배수에 해당하는 수를 모두 지운다.

 

import java.util.Scanner;
public class d019_Q1929 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int M = sc.nextInt();
		int N = sc.nextInt();
		
		int[] prime = new int[N + 1];
		
		for(int i = 2; i <= N; i++) {
			prime[i] = i;
		}//0과 1은 소수가 아니다.
		
		for(int i = 2; i <= N; i++) {
			if(prime[i] == 0) {continue;}
			for(int j = 2 * i; j <= N; j += i ) {
				prime[j] = 0;
			}
		}
		
		for(int i = M; i <= N; i++) {
			if(prime[i] != 0) {
				System.out.println(prime[i]);
			}
		}

		sc.close();
	}

}

 

에라토스테네스의 체를 이용해서 풀었다.

채점하는데 시간이 쫌 걸려서 맘졸였는데 맞았다.

이번 문제는 굉장히 도움이 됐던거 같다.