[JAVA] 백준 1929 - 소수 찾기2 (에라토스테네스의 체)

문제 풀이 전 이론 - 1

- 해당 문제는 소수 찾기1과 동일하지만, 입력에서 최악의 경우가 실행 시간에 치명적인 영향을 미친다.

- 기존의 방법으로 풀었으면 약수를 알아내는 시간 O($\sqrt{N}$)과 모든 N에 대한 O(N)로 인해 O(N$\sqrt{N}$)이 될 것이다.

- 일단 최악의 경우가 백만이라고 하면 의심해봐야 한다...(꿀팁)

- 이에 대한 문제를 효율적으로 해결할 수 있는 방법은 에라토스테네스의 체 알고리즘을 사용하는 것이다.

 

문제 풀이 전 이론 - 에라토스테네스의 체

- 1부터 N까지 범위 안에 들어가는 모든 소수를 구하려면 에라토스테네스의 체를 사용한다.

- 이를 이용하면 N이 100만인 경우 + 테스트케이스 문제일 때, 모든 소수를 크기가 100만인 배열에 미리 저장해놓고, 입출력할 수 있다.

- 에라토스테네스의 체 알고리즘은 아래와 같은 순서로 이루어져 있다.

- 1. 2부터 N까지 모든 수를 써놓는다.

- 2. 아직 지워지지 않은 수 중에서 가장 작은 수를 찾는다.

- 3. 그 수는 소수이다.

- 4. 이제 그 수의 배수를 모두 지운다.

 

- 2부터 100까지 모든 수를 써놓았다.

- 아직 지워지지 않은 수 중에서 가장 작은 수는 2이다.

- 2의 배수(빨간 글씨)를 찾아 모두 지운다.

- 아직 지워지지 않은 수 중에서 가장 작은 수는 3이다.

- 3의 배수(빨간 글씨)를 모두 지운다.

- 아직 지워지지 않은 수 중에서 가장 작은 수는 5이다.

- 5의 배수(빨간 글씨)를 모두 지운다.

- 보아하니, 다른 수 들은 2와 3의 배수로 인해 이미 모두 지워진 상태이고 (5 x 5~)만 지우면 된다.

- 아직 지워지지 않은 수 중에서 가장 작은 수는 7이다.

- 7의 배수(빨간 글씨)를 모두 지운다.

- 보아하니, 다른 수 들은 2와 3의 배수로 인해 이미 모두 지워진 상태이고 (7 x 7~)만 지우면 된다.

- 이제 다음은 11인데, 이미 2,3,5,7의 배수로 인해 이미 모두 지워졌으므로 (11 x 11~)만 지우면 되는데, 그러면 100을 넘어가므로 고려할 필요가 없다. 따라서 여기까지만 구하면 된다.

문제 풀이

- 에라토스테네스의 체 알고리즘을 구현한다.

- m과 n사이의 소수를 구하면 되므로, n+1만큼 크기의 배열을 선언한다.

- 지운 수는 true, 지워지지 않은 수(소수)는 false이다.

소스코드

public class Main {

	public static void main(String[] args) {
		//에라토스테네스의 체
		Scanner scan = new Scanner(System.in);
		int m,n;
		while(true) {
			m = scan.nextInt();
			n = scan.nextInt();
			if(m <= n) {
				break;
			}
		}
		boolean[] check = new boolean[n+1];
		
		EratosTenes(check, n);
		
		for(int i = m; i <= n; i++) {
			if(check[i] == false) {
				System.out.println(i);
			}
		}
	}
	
	public static void EratosTenes(boolean[] check, int n) {
		check[0] = check[1] = true;
		
		for(int i = 2; i*i <= n; i++) { //N이 100인 예시에서도 보았듯이 11부터는 굳이 배수를 구할 필요가 없다. 11*11은 100을 넘기기 때문 그리고 이미 지워야할 수들은 모두 지워짐.
			if(check[i] == true) {
				continue;
			}
			
		    for(int j = i+i; j<=n; j+=i) { // 2 , 3 본인들은 냅두고 J+=i로 배수만큼 반복 4,6 등은 이미 지워짐 i+i하면 소수인 본인들은 안지워짐.
		    	check[j] = true;
		    }
		}
	}
}

출력

느낀점

아직 몇 문제 풀어보진 않았지만 점점 문제를 노련하게 보는 눈이 생기고, 문제를 보자마자 효율성을 따져야 하는지 아니면 직관적으로 해석해서 풀어도 되는지 보이기 시작한다.