에라토스테네스의 체 (소수 구하기)

에라토스테네스의 체는 소수 구하고자 할 때 사용되는 알고리즘이다.

에라토스테네스의 체 원리

1. 구하고자 하는 소수의 범위만큼 1차원 배열을 생성한다.
2. 2부터 시작하고 현재 숫자의 배수의 해당하는 수를 끝까지 탐색하면서 지운다. (현재 숫자는 지우지 않는다.)
3. 이미 지워진 숫자는 건너 뛴다.
4. 배열 끝까지 반복하여 배열에 남아있는 모든 수를 출력한다.

20까지의 소수를 구하는 과정을 보자

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20

2의 배수를 삭제

1	2	3	~4~	5	~6~	7	~8~	9	~10~
11	~12~	13	~14~	15	~16~	17	~18~	19	~20~

3의 배수 삭제

1	2	3	~4~	5	~6~	7	~8~	~9~	~10~
11	~12~	13	~14~	~15~	~16~	17	~18~	19	~20~

5의 배수 삭제

1	2	3	~4~	5	~6~	7	~8~	~9~	~10~
11	~12~	13	~14~	~15~	~16~	17	~18~	19	~20~

7의 배수 삭제

1	2	3	~4~	5	~6~	7	~8~	~9~	~10~
11	~12~	13	~14~	~15~	~16~	17	~18~	19	~20~

11의 배수, 13의 배수, 17의 배수, 19의 배수 삭제

...

이런식으로 모든 경우의 수를 다 돌면서 소수를 구하는 방법은 비효율적이다. 위의 알고리즘은 O(N)의 시간복잡도를 가진다.
이를 훨씬 효율적으로 구할 수 있는 방법이 있다.

바로 모든 수를 돌면서 반복하는 것이 아닌 구하려고 하는 수의 제곱근 까지만 구하는 것이다.

예를 들어 120의 제곱근 = 10.95... 이므로 10까지만 반복한다.
N의 제곱근 이상의 숫자를 제곱한 값은 N보다 크기 때문에 더 이상의 연산은 의미가 없다.

따라서 다시 위의 예시를 보자면

20의 제곱근은 4.xx 이므로 4까지만 반복하면 소수를 구할 수 있다.

2의 배수를 삭제

1	2	3	~4~	5	~6~	7	~8~	9	~10~
11	~12~	13	~14~	15	~16~	17	~18~	19	~20~

3의 배수 삭제

1	2	3	~4~	5	~6~	7	~8~	~9~	~10~
11	~12~	13	~14~	~15~	~16~	17	~18~	19	~20~

결론적으로 20의 소수는 2, 3, 5, 7, 11, 13, 17, 19 가 된다.

class Solution {
    public int solution(int n) {
        int answer = 0;
        boolean[] so = new boolean[n + 1];
        so[0] = true;
        so[1] = true;
        for(int i = 2; i < Math.sqrt(n); i++){
            if(so[i]) continue;
            for(int j = 2*i; j < so.length; j+= i){
                so[j] = true;
            }
        }
        for(boolean s : so){
            if(!s) answer++;
        }
        return answer;
    }
}