Atkin의 체(Sieve of Atkin)는 지정된 정수까지의 모든 소수를 찾는 현대적인 알고리즘입니다. 고전적인 에라토스테네스의 체와 달리, Atkin의 체는 이차 형식(quadratic form)의 해의 개수를 활용해 소수 후보를 수학적으로 판별하므로 이론적으로 더 높은 효율을 기대할 수 있습니다. 이 글에서는 주어진 범위 내의 소수를 생성하기 위해 Atkin의 체를 C++로 구현하는 방법을 단계별로 살펴봅니다.
알고리즘
Atkin의 체의 전체 동작 과정은 다음과 같습니다.
시작
결과 리스트를 생성하고 2, 3, 5로 채운다.
체(sieve) 배열을 false 값으로 초기화한다.
다음 조건 중 하나라도 만족하면 sieve[n]을 true로 표시한다:
a) n = (4·x²) + (y²)의 해가 홀수 개이고 n % 12 = 1 또는 n % 12 = 5인 경우
b) n = (3·x²) + (y²)의 해가 홀수 개이고 n % 12 = 7인 경우
c) n = (3·x²) − (y²)의 해가 홀수 개이고 x > y이며 n % 12 = 11인 경우
모든 제곱수의 배수를 소수가 아닌 것으로 표시한다.
sieve[] 배열을 이용해 소수를 출력한다.
끝
핵심 아이디어는 세 가지 이차 형식에 대해 가능한 모든 (x, y) 조합을 검사하면서, 각 n에 대해 XOR 연산(sieve[n] ^= true)을 적용하는 것입니다. 이렇게 하면 해의 개수가 홀수인 n만 최종적으로 true로 남게 되며, 이러한 n이 소수 후보가 됩니다.
예제 코드
다음은 위 알고리즘을 그대로 구현한 전체 C++ 코드입니다.
#include <bits/stdc++.h>
using namespace std;
int SieveOfAtkin(int lmt) {
if (lmt > 2)
cout << 2 << " ";
if (lmt > 3)
cout << 3 << " ";
bool sieve[lmt];
for (int i = 0; i < lmt; i++)
sieve[i] = false;
for (int a = 1; a * a < lmt; a++) {
for (int b = 1; b * b < lmt; b++) {
// Main part of Sieve of Atkin
int n = (4 * a* a) + (b * b);
if (n <= lmt && (n % 12 == 1 || n % 12 == 5))
sieve[n] ^= true;
n = (3 * a * a) + (b * b);
if (n <= lmt && n % 12 == 7)
sieve[n] ^= true;
n = (3 * a * a) - (b * b);
if (a > b && n <= lmt && n % 12 == 11)
sieve[n] ^= true;
}
}
for (int r = 5; r * r < lmt; r++) {
if (sieve[r]) {
for (int i = r * r; i < lmt; i += r * r)
sieve[i] = false;
}
}
for (int x = 5; x < lmt; x++)
if (sieve[x])
cout << x << " ";
}
int main(void) {
int lmt = 30;
SieveOfAtkin(lmt);
return 0;
}
코드의 주요 흐름은 다음과 같습니다.
- 2와 3은 예외적으로 먼저 출력합니다.
- 중첩 반복문으로 모든 (a, b) 조합에 대해 세 가지 이차 형식을 계산하고, 나머지 조건(n % 12)에 맞는 경우 XOR 연산으로 체를 갱신합니다.
- 이후 5부터 √lmt까지의 후보 r에 대해 r²의 배수를 모두 소수가 아닌 것으로 표시하여 합성수를 제거합니다.
- 마지막으로 체 배열에서 true로 남은 값들을 순서대로 출력합니다.
실행 결과
위 프로그램을 실행하면 30 미만의 모든 소수가 출력됩니다.
2 3 5 7 11 13 17 19 23 29
시간 및 공간 복잡도
위와 같이 구현한 기본 버전의 Atkin의 체는 O(N)의 시간 복잡도와 O(N)의 공간 복잡도를 가집니다. 비트 연산과 세그먼트 기법 등을 추가로 최적화하면 이론상 O(N / log log N)까지 성능을 끌어올릴 수 있으며, 이는 매우 큰 범위에서 소수를 찾을 때 유리합니다.