에라토스테네스의 체
에라토스테네스의 체은 상한 N 이하의 모든 소수를 합성수의 배수를 지우는 방식으로 구한다 소수 탐색 분야의 대표적인 알고리즘 또는 핵심 계산 문제로, 자료 표현과 입력 조건에 맞는 계산 절차를 사용한다. 명시적인 수학적 불변식·상태 정의를 바탕으로 구현하므로 단순한 명령어 조합과는 구별...
| 분류 | 알고리즘 · 소수 탐색 |
|---|---|
| 핵심 문제 | 상한 N 이하의 모든 소수를 합성수의 배수를 지우는 방식으로 구한다 |
| 방법 | 2부터 시작해 아직 지워지지 않은 수 p를 소수로 판단하고 p²부터 p의 배수를 지운다 |
| 계산 비용 | 시간 O(N log log N), 공간 O(N) |
| 적용 조건 | N의 범위와 0·1이 소수가 아니라는 처리, 정수 곱 오버플로를 고려해야 한다 |
| 관련 활용 | 많은 소수의 일괄 열거와 약수 전처리에 유용하다 |
| 관련 이론 | 자료구조, 계산 복잡도 |
| 참고 자료 | CP-Algorithms |
에라토스테네스의 체은 상한 N 이하의 모든 소수를 합성수의 배수를 지우는 방식으로 구한다 소수 탐색 분야의 대표적인 알고리즘 또는 핵심 계산 문제로, 자료 표현과 입력 조건에 맞는 계산 절차를 사용한다. 명시적인 수학적 불변식·상태 정의를 바탕으로 구현하므로 단순한 명령어 조합과는 구별된다.[1]
계산 절차는 2부터 시작해 아직 지워지지 않은 수 p를 소수로 판단하고 p²부터 p의 배수를 지운다. p²가 N을 넘으면 더 이상 새로운 배수 표시가 필요하지 않다. 각 단계의 상태가 무엇을 의미하는지 정의하고 초기값과 경계 입력을 검사하면 결과의 정확성을 증명하거나 테스트할 수 있다.
복잡도는 시간 O(N log log N), 공간 O(N) 적용 전제는 N의 범위와 0·1이 소수가 아니라는 처리, 정수 곱 오버플로를 고려해야 한다 실제 연산량·메모리 사용은 구현의 자료구조와 정수·실수 표현, 전처리 및 입력 크기에 따라 달라진다.
응용과 관련 기법을 보면 많은 소수의 일괄 열거와 약수 전처리에 유용하다. 매우 큰 구간은 구간 체로 메모리 사용을 줄인다. 같은 문제라도 최악 시간 보장, 메모리 요구 사항과 정밀도·확률적인 실패 가능성에 따라 적합한 알고리즘이 달라진다.[2]