[알고리즘] 에라토스테네스의 체 - JAVA

12 Jun 2023 in TIL on 알고리즘

에라토스테네스의 체

내용

에라토스테네스의 체는 소수를 찾는 방법 중 하나이다.

1. 2부터 자기 자신을 제외한 2의 배수를 모두 지운다.

2. 남아있는 수 중 3은 소수이므로 3을 제외한 3의 배수를 모두 지운다.

3. 남아있는 수 중 5는 소수이므로 5를 제외한 5의 배수를 모두 지운다.

4. 위의 과정을 반복한다.

코드

// N까지의 소수를 구하기 위한 배열
boolean[] prime = new boolean[N + 1];

// 소수를 false라고 하자
// 0과 1은 소수가 아니므로 true
prime[0] = prime[1] = true;

// 2부터 자신의 배수를 지운다
for (int i = 2; i * i <= N; i++) {
    // i가 소수라면 자신의 배수를 지운다
    if (!prime[i]) {
        for (int j = i * i; j <= N; j += i) {
            prime[j] = true;
        }
    }
}