에라토스테네스의 체란?
에라토스테네스의 체(Sieve of Eratosthenes)는 2부터 N까지의 모든 소수를 한 번에 빠르게 찾아내는 고전 알고리즘입니다. 수를 하나씩 소수 판정하는 대신, 소수를 찾을 때마다 그 배수를 전부 지워 합성수를 걸러냅니다.
핵심 한 줄: "소수의 배수는 소수가 아니다." 작은 수부터 훑으며 배수를 지워나가면, 끝까지 살아남은 수가 소수입니다.
동작 원리
1단계. 2부터 N까지 모두 "소수 후보"로 표시합니다(불리언 배열 true).
2단계. p = 2부터 시작합니다. p가 아직 소수 후보면, p의 배수 p², p²+p, p²+2p, ...를 모두 "소수 아님"으로 지웁니다.
3단계. p를 1씩 늘리며 반복합니다. p가 √N을 넘으면 멈춥니다 — 그보다 큰 합성수는 이미 작은 소수가 다 지웠습니다.
4단계. 끝까지 true로 남은 수들이 N 이하의 모든 소수입니다.
알고노트 시각화는 소수가 정해질 때마다 그 배수들이 격자에서 차례로 지워지는 모습을 단계별로 보여줍니다.
왜 p²부터 지우나?
p의 배수 중 p보다 작은 계수를 가진 것들(2p, 3p, ..., (p-1)p)은 이미 더 작은 소수(2, 3, …)가 지웠습니다. 그래서 새로 지울 첫 배수는 p × p = p²부터면 충분합니다. 이 작은 최적화가 불필요한 반복을 크게 줄입니다.
마찬가지로 p > √N이면 p²> N이라 지울 배수가 범위 안에 없으니 멈춰도 됩니다.
시간복잡도와 공간복잡도
| 복잡도 | |
|---|---|
| 시간 | O(N log log N) |
| 공간 | O(N) |
거의 선형에 가까운 속도로, 수십~수백만 범위의 소수를 순식간에 구합니다.
예시로 따라가기
N = 20:
- •p=2: 4, 6, 8, …, 20 지움
- •p=3: 9, 12, 15, 18 지움
- •p=4: 이미 지워짐(건너뜀)
- •p=5: 5 > √20 ≈ 4.47 → 멈춤
- •남은 수: 2, 3, 5, 7, 11, 13, 17, 19 → 모두 소수
자주 하는 실수
- •2p부터 지우기: 틀리진 않지만
p²부터보다 비효율적입니다. - •경계 오프바이원:
p ≤ √N또는p*p ≤ N조건을 정확히 써야 합니다. - •1 처리: 1은 소수가 아니므로 처음부터 후보에서 제외하세요.
알고노트에서 직접 확인하세요
소수가 하나 정해질 때마다 그 배수가 격자에서 지워지고, 마지막에 소수만 남는 과정을 알고노트에서 단계별로 확인할 수 있습니다.