에라토스테네스의 체
소수가 되는 수의 배수를 지우면 남은 건 소수가 된다.
아래는 위키백과에 나온 에라토스테네스의 체를 이용해 소수를 구하는 방법이다.
- 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.
- 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
- 자기 자신을 제외한 2의 배수를 모두 지운다.
- 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
- 자기 자신을 제외한 3의 배수를 모두 지운다.
- 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
- 자기 자신을 제외한 5의 배수를 모두 지운다.
- 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
- 자기 자신을 제외한 7의 배수를 모두 지운다.
- 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.
위의 그림의 경우, \( 11^2 \) > 120이므로 11보다 작은 수의 배수들만 지워도 구할 수 있게 된다.
120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남은 수는 모두 소수이다.
코드로 구현
// N : 구하고자 하는 숫자 범위
int N;
boolean[] prime = new boolean[N + 1];
// 소수는 false로 표시, 0과 1은 소수가 아니다
prime[0] = true;
prime[1] = true;
for (int i = 2; i * i <= N; i++) {
// i가 소수라면
if (!prime[i]) {
// i의 배수는 모두 소수는 아니다
for (int j = i * 2; j <= N; j += i) {
prime[j] = true;
}
}
}
// 소수 출력
for (int i = 2; i <= N; i++) {
if (!prime[i])
System.out.print(i + " ");
}
728x90
반응형
'알고리즘 > 정수론' 카테고리의 다른 글
[백준] 14476번 최대공약수 하나 빼기 (JAVA) (0) | 2023.03.05 |
---|---|
[백준] 1837번 암호제작 (JAVA) (0) | 2023.03.05 |
[백준] 1735번 분수 합 (JAVA) (0) | 2023.03.04 |
[CS] 유클리드 호제법 (JAVA) (0) | 2023.03.03 |
[백준] 1644번 소수의 연속합 (JAVA) (0) | 2023.03.03 |