【C++】指定した範囲内の素数を生成する「セグメント篩（ふるい）」の実装方法

本記事では、セグメント篩（Segmented Sieve）を用いて、指定された範囲内の素数を効率的に生成するC++プログラムを紹介します。

セグメント篩は、まず単純なエラトステネスの篩（Simple Sieve）を使って √(high) 以下の素数をすべて求めます。その後、対象となる範囲 [low, high] を小さな区間（セグメント）に分割し、各セグメントごとに素数を順番に計算していくというのが基本的なアイデアです。

この手法の利点は、範囲全体に対するブール配列を一度に確保する必要がないため、メモリ使用量を大幅に削減できる点にあります。特に大きな数値範囲を扱う場合に有効です。

アルゴリズムの手順

Begin
    エラトステネスの単純な篩を用いて、limit 未満の
    すべての素数を見つける関数を作成する。
    セグメント篩を用いて、指定範囲内のすべての素数を求める。
    A) 単純な篩で high の平方根以下のすべての素数を計算する
    B) 指定範囲内の要素数を求める
    C) [low, high] の範囲に対してのみブール配列を宣言する
    D) [low ... high] 内で prime[i] の倍数となる最小の数を求める
    E) [low ... high] 内の prime[i] の倍数をマークする
    F) 範囲内でマークされていない数が素数である
End

C++コード例

#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関数

エラトステネスの篩を実装した関数です。2から limit までの数を順に走査し、まだマークされていない数を素数として vector に格納します。同時にその倍数をすべてマークすることで、合成数を除外していきます。

PrimeInRange関数

まず high の平方根 + 1 を上限として simpleSieve を呼び出し、基準となる素数のリストを取得します。次に [low, high] の範囲だけをカバーするブール配列 mark を用意し、各素数について範囲内の最初の倍数（下限）を計算した上で、その倍数をすべてマークします。

ポイントは lowLim = floor(low / prime[i]) * prime[i] の部分で、ここで low 以上となる最小の倍数を求めています。もし計算結果が low 未満であれば、prime[i] を加算して調整します。

最後に、mark 配列でマークされていない（＝どの素数の倍数でもない）数を出力します。これらが範囲内の素数となります。

計算量

セグメント篩の時間計算量は O((high − low + 1) × log log(high)) 程度であり、必要なメモリは O(√high + (high − low + 1)) です。通常のエラトステネスの篩のように high までの全領域を確保しなくてよいため、範囲が狭く数値が大きい場合に特に効率的です。