C++로 구현하는 세그먼트 체(Segmented Sieve) — 주어진 범위 사이의 소수 찾기

이 글에서는 세그먼트 체(Segmented Sieve) 알고리즘을 활용해 주어진 범위 사이의 소수를 생성하는 C++ 프로그램을 소개합니다. 세그먼트 체는 먼저 단순 체(Simple Sieve of Eratosthenes)를 이용해 √(n) 이하의 소수를 모두 구한 뒤, 전체 범위 [0 ... n-1]을 여러 개의 구간(segment)으로 나누고 각 구간별로 소수를 순차적으로 계산하는 방식입니다.

이러한 분할 처리 방식 덕분에 매우 큰 수 범위에서도 메모리 사용량을 크게 줄일 수 있어, 일반적인 에라토스테네스의 체보다 효율적으로 동작합니다.

알고리즘

시작
    에라토스테네스의 단순 체를 이용해 limit 이하의 모든 소수를
    찾는 함수를 작성한다.
    세그먼트 체를 이용해 주어진 범위 내의 모든 소수를 찾는다.
    A) 단순 체를 사용해 high의 제곱근 이하의 모든 소수를 계산한다.
    B) 주어진 범위에 포함된 원소의 개수를 센다.
    C) [low, high] 구간에 대해서만 불리언 배열을 선언한다.
    D) [low ... high] 범위에서 prime[i]로 나누어 떨어지는
       최소의 수를 찾는다.
    E) [low ... high] 범위에서 prime[i]의 배수들을 표시한다.
    F) 범위 내에서 표시되지 않은 수들이 곧 소수이다.
끝

예제 코드

#include <bits/stdc++.h>
using namespace std;
void simpleSieve(int lmt, vector<int>& prime) {
   bool mark[lmt + 1];
   memset(mark, false, sizeof(mark));
   for (int i = 2; i <= lmt; ++i) {
      if (mark[i] == false) {
         prime.push_back(i);
         for (int j = i; j <= lmt; j += i)
            mark[j] = true;
      }
   }
}
void PrimeInRange(int low, int high) {
   int lmt = floor(sqrt(high)) + 1;
   vector<int> prime;
   simpleSieve(lmt, prime);
   int n = high - low + 1;
   bool mark[n + 1];
   memset(mark, false, sizeof(mark));
   for (int i = 0; i < prime.size(); i++) {
      int lowLim = floor(low / prime[i]) * prime[i];
      if (lowLim < low)
         lowLim += prime[i];
      for (int j = lowLim; j <= high; j += prime[i])
         mark[j - low] = true;
   }
   for (int i = low; i <= high; i++)
      if (!mark[i - low])
         cout << i << " ";
}
int main() {
   int low = 10, high = 50;
   PrimeInRange(low, high);
   return 0;
}

실행 결과

11 13 17 19 23 29 31 37 41 43 47

코드 동작 원리 요약

simpleSieve() 함수는 high의 제곱근까지의 소수를 미리 구해 저장합니다. 이후 PrimeInRange() 함수는 각 소수의 배수 중 low 이상이 되는 가장 작은 값(lowLim)부터 시작해 범위 내 배수들을 모두 합성수로 표시하고, 마지막에 표시되지 않은 수만 출력함으로써 해당 구간의 소수를 얻습니다. 위 예제에서는 10부터 50 사이의 소수가 정상적으로 출력되는 것을 확인할 수 있습니다.