이 글에서는 순다람의 체(Sieve of Sundaram)를 이용하여 주어진 범위 사이의 소수를 생성하는 C++ 프로그램을 소개합니다. 순다람의 체는 1934년 인도의 수학자 순다람(Sundaram)이 발견한 알고리즘으로, 에라토스테네스의 체와 마찬가지로 합성수를 걸러내는 방식이지만 홀수만을 대상으로 처리하기 때문에 필요한 메모리가 절반으로 줄어드는 것이 특징입니다.
알고리즘
n보다 작은 소수를 모두 찾는 것이 목표입니다. 먼저 n-2를 절반으로 나눈 값을 New라 하고, i + j + 2ij(단, 1 ≤ i ≤ j) 형태의 수를 걸러내기 위한 배열 marked[]를 생성한 뒤 모든 요소를 false로 초기화합니다.
New = (n - 2) / 2;
- i를 1부터 New까지 반복하며, 각 단계에서 j = i로 설정합니다.
- (i + j + 2ij) ≤ New를 만족하는 동안 j를 1씩 늘려가며 marked[i + j + 2ij]를 true로 표시합니다.
- n이 2보다 크면 2를 첫 번째 소수로 출력합니다.
- 나머지 소수는 모두 2i + 1 형태입니다. 따라서 marked[i]가 false인 모든 i에 대해 2i + 1을 출력합니다.
동작 원리
이 알고리즘의 핵심은 홀수 합성수를 제거하는 데 있습니다. 두 홀수 (2i+1)과 (2j+1)을 곱하면 (2i+1)(2j+1) = 2(i + j + 2ij) + 1이 되므로, i + j + 2ij 형태의 인덱스는 곧 홀수 합성수에 대응합니다. 이들을 미리 표시해 두면 남은 인덱스 i에 대한 2i + 1은 반드시 소수가 됩니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
// m 미만의 모든 소수를 출력하는 함수
void SieveOfSundaram(int m) {
int N = (m - 2) / 2;
bool marked[N + 1];
memset(marked, false, sizeof(marked));
// i + j + 2ij 형태의 수를 모두 표시
for (int i = 1; i <= N; i++)
for (int j = i; (i + j + 2 * i * j) <= N; j++)
marked[i + j + 2 * i * j] = true;
// 2는 유일한 짝수 소수이므로 먼저 출력
if (m > 2)
cout << 2 << " ";
// 표시되지 않은 인덱스 i에 대해 2i + 1이 곧 소수
for (int i = 1; i <= N; i++)
if (marked[i] == false)
cout << 2 * i + 1 << " ";
}
int main(void) {
int m = 10;
SieveOfSundaram(m);
return 0;
}실행 결과
m = 10으로 실행하면 10 미만의 모든 소수가 출력됩니다.
2 3 5 7