이 노트는 여러 수의 소수 여부를 한 번에 계산할 때, 합성수의 구조를 이용해 표시 작업을 줄이는 과정을 설명합니다. 먼저 전체 체의 불변식과 p²의 근거를 확인하고, 이어 구간 체의 인덱스·범위·정수 안전성을 실제 작은 입력으로 대조합니다.
범위 반복 조회와 전처리 결과 공유
1부터 N까지 소수 여부를 반복해서 조회한다면 각 수를 따로 나누어 검사하는 대신 합성수 위치를 미리 표시할 수 있습니다. 에라토스테네스의 체는 작은 소수의 배수를 제거하고 남은 수를 소수로 판정합니다.
단일 아주 큰 수의 소수 판정과는 다른 문제입니다. 체는 최대 범위에 비례하는 메모리를 사용하므로 조회 한 번을 위해 거대한 배열을 만들면 비효율적일 수 있습니다. 전처리를 몇 번 재사용하는지까지 보고 선택합니다. 예를 들어 N=30을 열 번 질의하면 한 번 만든 배열을 재사용할 수 있지만, 10^12 부근의 짧은 구간 하나라면 전체 배열을 만들 수 없습니다. 이 선택은 “소수 판정 알고리즘”이 아니라 질의 범위·재사용 횟수·메모리 예산의 조합으로 결정합니다.
p² 시작점과 작은 소수 배수의 선행 제거
5의 배수를 지우는 차례라고 생각해 보겠습니다. 10은 이미 2의 배수를 지울 때 지웠고, 15는 3의 배수를 지울 때 지웠습니다. 20도 2의 배수입니다. 따라서 5부터 새로 확인해야 하는 첫 배수는 25입니다.
일반적으로 소수 p에 대해 2p, 3p, …, (p−1)p에는 p보다 작은 인수가 있습니다. 그 인수에 포함된 작은 소수를 처리할 때 이미 지워졌으므로, p²부터 시작해도 합성수를 놓치지 않습니다.
언제까지 반복해야 할까요? 합성수 n을 a×b로 썼을 때 두 인수가 모두 √n보다 클 수는 없습니다. 둘 다 크면 곱이 n을 넘기 때문입니다. 그래서 N 이하 합성수를 지우려면 √N 이하의 소수까지만 처리하면 됩니다. 코드의 p²≤N 조건은 이 사실에서 나옵니다.
| p | N=30에서 새로 순회하는 배수 | 남는 소수 후보 |
|---|---|---|
| 2 | 4,6,8,…,30 | 2와 홀수들 |
| 3 | 9,12,15,…,30 | 3의 배수 제거 |
| 5 | 25,30 | 25 제거 |
4는 이미 합성수라 별도 소수 단계로 처리하지 않습니다. 최종 소수는 2,3,5,7,11,13,17,19,23,29입니다. 0과 1은 처음부터 소수가 아닙니다. 작은 검산으로는 N=10에서 [2,3,5,7]만 남고, p=2 단계 뒤 4·6·8·10이 지워지며 p=3 단계에서 새로 9가 지워지는지 확인하면 됩니다. 이 추적은 p² 시작점 오류와 0·1 초기화 오류를 서로 다른 실패로 드러냅니다.
그림을 글로 읽기
- p=2 · 4부터 표시
- p=3 · 9부터 표시
- p=4 · 이미 합성수: 새 단계 생략
- p=5 · 25부터 표시
- p=2 · 4부터 표시 → p=3 · 9부터 표시: 다음 후보
- p=3 · 9부터 표시 → p=4 · 이미 합성수: 다음 후보
- p=4 · 이미 합성수 → p=5 · 25부터 표시: 건너뜀
전체 범위의 슈도코드
sieve(N):
require integer N and N >= 0
prime = [true] * (N+1)
prime[0] = false
if N >= 1: prime[1] = false
p = 2
while p <= N // p:
if prime[p]:
for multiple from p*p through N step p:
prime[multiple] = false
p += 1
return prime
루프 조건을 p<=N//p로 쓰면 조건 검사에서 p² overflow를 피하기 쉽습니다. 그 조건 아래의 p²는 N 이하이지만 N+1 크기 계산과 마지막 multiple+p도 고정 폭 타입에서 범위를 확인해야 합니다. 안전한 넓은 정수나 종료 전 덧셈 검사 등 실제 구현 계약이 필요합니다.
시간 O(N log log N), 공간 O(N)입니다. 비트 압축이나 홀수만 저장하면 상수 공간을 줄일 수 있지만 인덱스 변환과 2의 특별 처리가 추가됩니다. 조회마다 배열을 다시 만들면 전처리 재사용의 이점이 사라집니다.
구간 체의 첫 배수와 p² 시작점
먼저 sqrt(R) 이하의 작은 소수 목록을 만듭니다. 그 소수마다 구간 내부의 첫 배수를 구해 [L,R] 배열에 표시합니다. 첫 위치는 다음 두 조건을 동시에 만족해야 합니다.
start = max(p*p, ceil(L/p)*p)
이 식의 두 항은 서로 다른 일을 합니다. ceil(L/p)*p는 L 이상인 첫 배수를 찾습니다. 예를 들어 L=20, p=3이면 20을 넘는 첫 배수인 21입니다. 반면 p²는 앞에서 설명한 체의 시작점을 유지합니다.
둘 중 큰 값을 택하는 이유는 [2,5]를 보면 분명합니다. 2 이상인 첫 2의 배수는 2이지만, 거기부터 지우면 소수 2 자체를 없애 버립니다. p²인 4와 비교해 4부터 시작해야 합니다.
[20,30]에서는 2의 배수를 20부터, 3의 배수를 21부터, 5의 배수를 25부터 지웁니다. 마지막에 남는 23과 29가 이 구간의 소수입니다. 실제 배열의 인덱스는 원래 숫자에서 L을 뺀 값이므로, 21을 표시할 때는 result[1]을 바꿉니다.
segment(L,R,basePrimes):
require 0 <= L <= R
result = [true] * (R-L+1)
for p in basePrimes where p <= R//p:
q = L//p + (1 if L%p != 0 else 0)
start = max(p*p, q*p)
for x from start through R step p:
result[x-L] = false
for x in [0,1]:
if L <= x <= R: result[x-L] = false
return result
이 예는 basePrimes가 sqrt(R) 이하의 모든 소수를 포함하고 산술이 안전한 범위라는 전제입니다. q*p가 R보다 커도 표현 과정에서 overflow하지 않게 해야 합니다. 구간 길이가 작아도 sqrt(R)까지의 기초 소수 생성 비용은 남습니다. 구현 진단에서는 L=2, R=2처럼 소수 자체가 첫 배수 후보가 되는 구간, L=0, R=1처럼 전부 부재인 구간, L=20, R=30처럼 x-L 오프셋이 드러나는 구간을 별도로 기록합니다.
전처리·질의 비용 비교
| 요구 | 우선 고려 | 남는 비용 |
|---|---|---|
| 작은 N 이하 반복 조회 | 전체 체 | O(N) 상태 보관 |
| 큰 연속 범위를 차례로 처리 | 구간 체 | 기초 소수, 구간별 초기화·표시 |
| 매우 큰 수 하나 | 해당 크기에 맞는 소수 판정 | 결정적·확률적 보장과 정수 연산 |
구간 크기가 너무 작으면 소수 목록을 매번 순회하는 고정 비용이 커집니다. 너무 크면 메모리·캐시 비용이 늘어납니다. 구현에서 쓰는 bool 배열이 비트인지 바이트인지도 실제 메모리에 영향을 줍니다.
작은 구간과 기준 판정의 결과 대조
작은 범위의 각 수를 제곱근까지 나누는 기준 함수와 체의 결과를 먼저 맞춥니다. [0,0]에서는 0을 소수가 아니라고 표시하고, [1,2]에서는 1만 지워 2를 남깁니다. [2,5]에서는 2와 3과 5를 남겨 p² 시작점이 소수 자체를 지우지 않는지 보고, [20,30]에서는 result[1]이 원래 수 21에 해당하는지와 최종 소수 23·29를 확인합니다. 완전제곱수가 구간의 양끝에 오는 경우도 넣고 전체 체와 구간 체의 결과를 대조하면, 소수 목록 자체와 시작 배수·L 오프셋 오류를 나누어 찾을 수 있습니다.