アルゴリズム初心者向けの基礎と入門(C#, Pythonとか)

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

エラトステネスの篩(ふるい)とは、素数判定のアルゴリズムの一種です。このアルゴリズムは古代ギリシャの哲学者エラトステネス(紀元前275年 - 紀元前194年)が考案したため、その名を冠しています。 エラトステネスの篩は、指定された数 n 以下のすべての素数をすべて発見するアルゴリズムです。

素数判定とは、ある自然数 n が 素数か合成数かを判定する問題です。素数は暗号鍵の生成等に大きくかかわるため、効率的な素数判定のアルゴリズムは非常に重要です。

アルゴリズムの解説

エラトステネスの篩は以下の流れで素数を見つけ出します。

1. 素数候補リスト(2 .. n)を生成します。
2. 素数候補リストの先頭要素(m)を素数リストに追加します。
3. mの倍数を素数リストからふるい落とします(削除します)。
4. m+1 < √nになるまで 2～3 を繰り返します。
5. 素数候補リストに残っている要素をすべて素数リストに追加します。

なぜ √n 以下の数のみの判定か

ある合成数 p について考えたとき、

p = q * r

となる 約数の組(q, r)が存在しなければなりません(q <= r)。例として p=221の場合は、(q, r) = (13, 17) 等です。このとき q と r のいずれかは必ず √p 以上の値になっています。（仮に両方共 √p 未満の値であれば掛け合わせても p 以下の数になってしまうのでありえません。）

したがって、エラトステネスの篩で221を素数判定する場合、実際に割り算をして割り切れるかどうか判定するのは √n以下、つまり14以下の整数まででよいのです。なぜなら14以上の約数が存在する数であれば、より小さい約数ですでにふるい落とされているからです。

したがって、221以下の数に限って言えば、14以下の整数で割り切れなかった数については、15以上で割り切れるかどうかを確認するまでもなく、素数と判定できるということです。

サンプルコード

エラトステネスの篩を実装したサンプルコードです。2以上の自然数nを引数で渡し、n以下のすべての素数を返します。

C#

public static List<int> SieveOfEratosthenes(int n)
{
    // 素数を格納するリスト
    var primes = new List<int>();
    // 素数候補のリスト[2..n]
    var list = Enumerable.Range(2, n - 2).ToList();

    // 2以下の数の場合は空、2の場合は2を返す。
    if (n < 2) return primes;
    else if (n == 2) return new List<int>(2);

    // 素数候補をふるい落としながら素数を探す
    while (Math.Pow(list[0], 2) <= n)
    {
        var first = list[0];    // 先頭要素
        primes.Add(first);      // 先頭を素数リストへ
        list.RemoveAt(0);       // 先頭要素削除

        // 素数の倍数をふるい落とし
        list.RemoveAll(x => x % first == 0);
    }
    // 残りの探索リストをまとめて素数リストに追加
    primes.AddRange(list.ToArray());
    return primes;
}