큰 범위의 소수를 여러 번 조회하려 합니다. 매번 나눗셈 검사하는 것과 체를 만드는 것은 어떻게 다른가요?

한 번의 큰 수 소수 판정과 일정 범위의 소수를 여러 번 조회하는 문제를 나누겠습니다. 단일 수는 제곱근까지 나눠 보는 방식이 간단할 수 있지만, 범위의 모든 수를 반복해서 판정하면 같은 나눗셈을 되풀이합니다. 에라토스테네스의 체는 작은 소수의 배수를 한 번에 표시해 전처리 비용을 여러 질의가 공유하도록 합니다.

범위·질의 수·메모리를 비교합니다

2부터 시작해 아직 지워지지 않은 수를 소수로 보고 그 배수를 합성수로 표시합니다. 소수 p의 p²보다 작은 합성수 배수는 더 작은 소수 단계에서 이미 지워졌으므로 p²부터 표시할 수 있습니다. p²가 최대 범위를 넘는 순간 이후의 합성수는 이미 처리됐으므로 제곱근까지의 소수만 사용하면 됩니다. 0과 1은 소수가 아니므로 처음부터 제외합니다. 이처럼 범위 전체의 판정 결과를 미리 만들어 재사용하는 것을 전처리 기반 질의(preprocessing-based query)라고 부릅니다.

최대값 N까지 배열을 두면 공간은 O(N)이고, 에라토스테네스의 체의 시간은 O(N log log N)입니다. N이 매우 크고 일부 구간만 필요하면 작은 소수 목록을 먼저 만든 뒤 [L, R] 구간의 배수를 표시하는 segmented sieve를 사용해 메모리를 줄일 수 있습니다. 구간 시작 이상인 첫 배수와 p²를 비교해 표시 시작 위치를 계산해야 하고, p*p와 배수 계산이 정수 범위를 넘지 않는지 확인하겠습니다. 홀수만 저장하면 메모리는 줄지만 인덱스 변환과 2 처리 규칙이 추가됩니다.

질의 수와 숫자 크기를 비교합니다

범위 내 모든 수를 여러 번 조회하거나 소수 목록을 반복 사용할 때 체의 초기 비용이 정당화됩니다. 반대로 한 번만 매우 큰 수를 판정한다면 범위 배열을 만드는 것은 부적합하고, 작은 나눗셈 검사나 확률적 판정법을 용도에 맞게 선택합니다. 확률적 판정은 결과 오류가 허용되는지와 검증 단계가 있는지를 먼저 정해야 합니다.

테스트는 0·1·2, 완전제곱수, 소수와 합성수, 범위 양끝, 구간 체의 경계를 포함합니다. 작은 N은 각 수를 제곱근까지 나누는 기준 구현과 결과를 비교하고, 실행 시간·메모리·전처리 재사용 횟수를 측정하겠습니다. 제곱부터 표시한다는 최적화가 정확성을 바꾸는 것이 아니라 이미 처리된 배수를 건너뛰는 것임을 설명할 수 있어야 합니다.

에라토스테네스의 체는 2부터 시작해 아직 지워지지 않은 p를 소수로 보고 p²부터 배수를 지웁니다. p²보다 작은 합성수 배수는 더 작은 소수 단계에서 이미 처리됐기 때문입니다. 최대 N까지 체의 시간은 O(N log log N), 공간은 O(N)이며, 여러 범위 질의가 같은 전처리를 재사용할 때 이 비용을 지불할 가치가 있습니다.

구간 [L,R]에서는 각 소수 p의 첫 표시 위치를 max(p², ceil(L/p)·p)로 잡습니다. ceil(L/p)·p만 쓰면 p 자체를 지울 수 있고, p²부터 무조건 시작하면 구간 밖 인덱스를 쓰거나 불필요한 배수를 순회할 수 있으므로 둘 중 큰 값을 택합니다. L이 0·1을 포함하면 별도 제외하고, 제곱·배수 오버플로와 구간 경계를 기준 구현과 비교하겠습니다.

예를 들어 구간 [20,30]에서 p=3이면 첫 표시는 max(9,21)=21, p=5이면 max(25,20)=25입니다. 구간 시작보다 작은 배수를 배열에 쓰지 않고 소수 p 자체도 지우지 않습니다. 구간마다 작은 소수 목록을 재사용하며, 정수 올림 계산 (L+p-1)/p도 L+p-1의 오버플로를 피하는 표현이나 넓은 정수 타입을 선택하겠습니다.