소수(Prime Number) - 에라토스테네스의 체 (Java)

 

○ 소수

- 1과 자기 자신만을 약수로 가지는 수

 

 

○ 소수 구하기 - 에라토스테네스의 체

소수 관련 문제를 풀 때 가장 자주 사용되는 방법은 에라토스테네스의 체이다. 

다음은 에라토스테네스의 체는 소수를 찾는 간단한 알고리즘을 시각적으로 표현한 것이다. (위키피디아 참고)

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

○ 에라토스테네스의 체 구현

2부터 시작하여 자신의 배수가 되는 수를 지워나가면 되는데 만약 120까지의 소수를 구한다고 하면

이므로 11보다 작은 수의 배수들만 지워도 충분하다.

public class Prime {
 
    public static void main(String[] args) {
        int n = 120;
        boolean[] isPrime = new boolean[n+1];
        Arrays.fill(isPrime , true);
        
        // 소수는 true
        // 0, 1은 소수가 아니므로 false
        isPrime [0] = isPrime [1] = false;
        for(int i = 2; i * i <= n; i++){
            // 만약 i가 소수 혹은 아직 지워지지 않았다면
            if (isPrime[i]){
                // i의 배수 j들에 대해 isPrime[j] = false; 로 둔다.
                // i*i미만의 배수는 이미 지워졌으므로 신경쓰지 않는다.
                for(int j=i * i; j <= n; j += i) {
                    isPrime[j] = false;                
                }
            }        
        }    
        // 1 ~ 120 사이의 소수 출력
        for(int i = 1; i <= n ;i++){
            if(isPrime[i]) System.out.print(i + " ");        
        }
    }
}

1) 지워지지 않은 수를 찾을 때 n이 아니라 n의 1/2제곱까지만 찾는다. 이것은 위의 소수 판정 알고리즘과 동일한 방식이다.

2) i의 배수들을 모두 지울 때 i * 2에서 시작하지 말고 i * i에서 시작한다. 2 * i는 이미 2의 배수를 지울 때 지워졌고

   3 * i는 이미 3의 배수를 지울 때 지워졌기 때문이다.

3) i * k (k < i)까지는 이미 검사되었으므로 j시작 값은 i * 2에서 i * i로 개선할 수 있다. (k의 최댓값은 i - 1이므로)

4) 만약 isPrime[i]가 true이면, i 이후의 i 배수는 약수로 i를 가지고 있는 것이 되므로 모두 true값을 준다.

5) 만약 isPrime[i]가 false이면, i는 이미 소수가 아니므로 i의 배수 역시 소수가 아니게 되므로 검사하지 않아도 된다.