[공식] 소수 찾기 / 에라토스테네스의 체

"소수가 되는 수의 배수를 지우면 남은 것은 모두 소수이다."

1. 2부터 시작해 소수를 구하고자 하는 구간의 모든 수를 나열한다.
2. 2는 소수이므로 남겨둔다.
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아있는 수 가운데 3은 소수이므로 3은 남겨둔다.
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6. 남아있는 수 가운데 5는 소수이므로 5는 남겨둔다.
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8. 남아있는 수 가운데 7은 소수이므로 7은 남겨둔다.
9. 자기 자신을 제외한 7의 배수를 모두 지운다.
10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.
    (출처: 위키백과)

위 그림을 보면
2부터 120까지의 수 중 소수를 구할 때, 11보다 작은 수의 배수를 지우고 남은 수는 모두 소수인 것을 확인할 수 있다. (2,3,5,7의 배수들을 지우고 남은 수는 모두 소수임)

즉 2에서 N까지의 수 중에서 소수를 구한다고 할 때, N의 제곱근보다 작은 소수들의 배수를 모두 지우면, 남은 수들은 전부 소수가 된다. (위 그림의 경우 10<√120<11 이므로 11보다 작은 소수인 2,3,5,7의 배수를 지우면 남은 수는 모두 소수)

Java 구현

public class Eratostenes {
	void showPrimeNumbers(int n){
    boolean[] prime = new boolean[n+1];
    // 0과 1은 소수가 아님
    prime[0] = prime[1] = false;
    for(int i=2;i<=n;i++) {
    	prime[i]=true;
    }
    
    // 2~n의 제곱근보다 작은 소수들의 배수를 제외시킨다.
    for(int i=2;i*i<=n;i++){
    	for(int j=i*i;j<=n;j+=i) {
        	prime[j]=false;
        }
    }
    
    //소수 출력
    for(int i=2;i<=N;i++) {
    	if(prime[i]) System.out.println(i);
    }
}