C++で素数を見つける最速のアルゴリズムとは？エラトステネスの篩を徹底解説

nがおよそ1000万以下の規模である場合、n未満の素数を高速に求める方法として、最も効率的なアルゴリズムのひとつが「エラトステネスの篩（ふるい）」です。この手法は計算量がO(n log log n)と非常に効率的で、競技プログラミングから実務まで幅広く活用されています。

エラトステネスの篩とは

エラトステネスの篩は、古代ギリシャの数学者エラトステネスによって考案された古典的な素数列挙アルゴリズムです。2からnまでの整数を順に走査し、それぞれの素数の倍数を順次「ふるい落とす」ことで、最終的に残った数だけを素数として抽出します。

サンプルプログラム

以下は、エラトステネスの篩をC++で実装したプログラムの例です。

#include <bits/stdc++.h>
using namespace std;

void SieveOfEratosthenes(int num) {
    bool pno[num + 1];
    memset(pno, true, sizeof(pno));
    for (int i = 2; i * i <= num; i++) {
        if (pno[i] == true) {
            for (int j = i * 2; j <= num; j += i)
                pno[j] = false;
        }
    }
    for (int i = 2; i <= num; i++)
        if (pno[i])
            cout << i << " ";
}

int main() {
    int num = 15;
    cout << "The prime numbers smaller or equal to " << num << " are: ";
    SieveOfEratosthenes(num);
    return 0;
}

実行結果

上記プログラムの出力は以下のとおりです。

The prime numbers smaller or equal to 15 are: 2 3 5 7 11 13

プログラムの解説

それでは、上記プログラムの動作を詳しく見ていきましょう。

SieveOfEratosthenes() 関数

SieveOfEratosthenes() 関数は、引数として受け取った num 未満のすべての素数を求めます。まず、num+1 のサイズを持つブール型配列 pno を用意し、memset() ですべての要素を true で初期化します。その後、2から順に走査し、i が素数であれば i の倍数をすべて false に設定していきます。

ここで注目すべきは、外側のループ条件を i*i <= num としている点です。任意の合成数の最小の素因数は必ず √num 以下になるため、√num まで調べれば十分だからです。最後に、true のまま残っているインデックス、すなわち素数のみを出力します。

void SieveOfEratosthenes(int num) {
    bool pno[num + 1];
    memset(pno, true, sizeof(pno));
    for (int i = 2; i * i <= num; i++) {
        if (pno[i] == true) {
            for (int j = i * 2; j <= num; j += i)
                pno[j] = false;
        }
    }
    for (int i = 2; i <= num; i++)
        if (pno[i])
            cout << i << " ";
}

main() 関数

main() 関数では、変数 num に上限値を設定し、SieveOfEratosthenes() を呼び出すことで、num 以下のすべての素数を出力しています。

int main() {
    int num = 15;
    cout << "The prime numbers smaller or equal to " << num << " are: ";
    SieveOfEratosthenes(num);
    return 0;
}

まとめ

エラトステネスの篩は、nが約1000万程度までの範囲であれば、非常に高速に素数を列挙できる優れたアルゴリズムです。シンプルな実装ながら計算量 O(n log log n) を実現できるため、「指定された範囲内の素数をすべて求めたい」という場面では第一の選択肢となります。なお、さらに大きな数の素数判定が必要な場合には、Miller–Rabin法などの確率的素数判定法や、必要な区間だけを処理する「区間ふるい」の利用も検討するとよいでしょう。