[백준]소수찾기_1978 #에라토스테네스의 체 #Sieve of Eratosthenes #JAVA

소수라고 하면 1과 자기 자신으로만 나누어지는 수를 말한다. 이를 찾는 방법중에 가장 오래되고 알고리즘 적으로 많이 사용되는 에라토스테네스(아리스토텔레스)의 체에 대해 알아보고 JAVA로 구현하는 까지 해 보겠다. 

 

에라토스테네스의 체란?

알고리즘

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
9. 자기 자신을 제외한 7의 배수를 모두 지운다.
10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

그림의 경우,  11^2>120

이므로 11보다 작은 수의 배수들만 지워도 충분하다. 즉, 120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수이다.

 

package baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
//에라토스테네스의 체를 이용한 소수 구하기
public class FIndDecimal_1978 {
	static int maxNum = 1000;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int totalRequestCount = 0;
		boolean[] isDecimal = new boolean[maxNum +1];
		int result = 0;
		
		Arrays.fill(isDecimal, true);
		// 0과 1은 소수가 아님으로 false
		isDecimal[0] = false;
		isDecimal[1] = false;
		sieveOfEratosthenes(isDecimal);
		totalRequestCount = Integer.valueOf(br.readLine());
		String[] request = br.readLine().split(" ");
		for(int i=0; i<totalRequestCount; i++) {
			if(isDecimal[Integer.valueOf(request[i])]) {
				result++;
			}
		}
		System.out.print(result);
		
	}
	//가장 작은 소수인 2부터 배수를 확인함으로써 소수가 아닌 수를 걸러낸다.
	//i가 소수일 경우 소수를 구하는 범위(maxNum)가 i*i보다 작거나 같은 경우의 i의 배수를 배교해 보면 된다. ex) 130일 경우 11*11=121 이므로  1 ~ 130까지는 11보다 큰 소수로만 이루어진 수가 없다. 즉 2, 3, 5, 7, 11로 나누어 떨어지지 않는 수는 모두 소수이다.  
	static void sieveOfEratosthenes(boolean[] isDecimal) {
		for(int i=2; i*i<=maxNum; i++) {
			if(isDecimal[i]) {
				for(int j=i+1; j<=maxNum;j++) {
					if(j%i == 0) {
						isDecimal[j] = false;
					}
				}
			}
		}
	}
}