에라토스테네스의 체
에라토스테네스의 체
수학에서 에라토스테네스의 체는 소수를 찾는 빠르고 쉬운 방법이다. 고대 그리스 수학자 에라토스테네스가 발견하였다.
www.google.com
자바 코드
// maxV는 최댓값
boolean[] isPrime = new boolean[maxV + 1];
Arrays.fill(isPrime, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i <= maxV; i++) {
if (isPrime[i]) {
for (int j = i * i; j <= maxV; j += i)
isPrime[j] = false;
}
}
i * i가 maxV보다 작거나 같은 값까지 실행하는 이유는?
만약 n보다 작은 어떤 수 m이 라면 와 b 중 적어도 하나는 루트n 이하이다. 즉, n보다 작은 합성수 m은 루트보다
작은 수의 배수만 체크해도 전부 지워진다는 의미이므로, 루트 이하의 수의 배수만 지우면 된다.
'Algorithm' 카테고리의 다른 글
| 행렬 제곱 (백준 10830번) (0) | 2025.12.15 |
|---|