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

소수란? 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수

에라토스테네스의 체란?

소수를 구하는 알고리즘

"소수가 되는 수의 배수를 지우면 남은 건 소수가 된다"를 이용한 알고리즘

• 2부터 자기 자신을 제외한 자신의 배수가 되는 수를 지우면 된다.

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.
2. 소수가 되는 수의 배수를 지우면 남은 건은 소수만 된다
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아 있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다.
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6. 남아 있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다.
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8. 위 과정을 반복한다.

자바로 구현

// N 이하의 소수를 구한다
boolean[] prime = new boolean[N + 1];

// 소수는 false
// 0 과 1은 소수가 아니므로 제외
prime[0] = prime[1] = true; // 소수 아님

for (int i = 2; i * i < prime.length; i++) {
	if (prime[i]) continue;
    for (int j = i * i; j < prime.length; j += i) {
        prime[j] = true;
	}
}