【C++】エラトステネスのふるいを実装して指定範囲の素数を生成する方法

本記事では、エラトステネスのふるい（Sieve of Eratosthenes）を実装し、指定された範囲内の素数を生成するC++プログラムを紹介します。

エラトステネスのふるいとは

エラトステネスのふるいは、古代ギリシャの数学者エラトステネスによって考案された、素数を効率的に求めるための古典的なアルゴリズムです。ある範囲内のすべての素数を見つけたい場合に特に有効な手法として知られています。

この手法では、まずすべての要素を0で初期化した整数型の配列を用意します。続いて、ネストされた二重ループの中で、素数ではない数（合成数）に対応するインデックスを1としてマークしていきます。そして最後に、インデックスが0のまま残っている要素こそが素数であると判定できるという仕組みです。

アルゴリズムの手順

開始
　　サイズnの配列を宣言し、すべての要素をゼロで初期化する
　　length、i、j を宣言する
　　length を読み込む
　　i = 2 から n-1 まで繰り返す
　　　　j = i*i から n-1 まで i ずつ増加させながら繰り返す
　　　　　　Arr[j-1] = 1
　　　　繰り返し終了
　　繰り返し終了
　　i = 1 から n まで繰り返す
　　　　もし arr[i-1] == 0 ならば
　　　　　　i を出力する
　　繰り返し終了
終了

ポイントは、内側のループを i*i から開始している点です。それ未満の合成数は、より小さい素因数の段階ですでにマーク済みであるため、この工夫により無駄な計算を省き、処理を高速化できます。

サンプルコード

#include <iostream>
const int len = 30;

int main() {
    int arr[30] = {0};

    // 合成数のインデックスをマーク
    for (int i = 2; i < 30; i++) {
        for (int j = i * i; j < 30; j += i) {
            arr[j - 1] = 1;
        }
   &;}

   &;// マークされていない数（素数）を出力
   &;for (int i = 1; i < 30; i++) {
        if (arr[i - 1] == 0)
            std::cout << i << "\t";
   &;}
}

実行結果

1    2    3    5    7    11    13    17    19    23    29

補足：1の扱いについて

数学的に1は素数ではないため、厳密な定義に従う場合は出力用ループを i = 2 から開始するとよいでしょう。そうすることで、正確な素数の一覧のみを出力できます。

まとめ

エラトステネスのふるいは、配列を使って合成数を順に除外していくシンプルかつ強力なアルゴリズムです。計算量は O(n log log n) と非常に効率的で、競技プログラミングや数学的処理の基礎としても頻繁に活用されています。ぜひ実際にコードを動かして、その仕組みを体感してみてください。