最速の素数列挙プログラム C#

Code IQなどのアルゴリズムを問う問題で、素数を使うものが頻繁に出題される。
そういう時に迷わず使えるように、現時点で最速の素数列挙プログラムを残しておこうと思います。

エラトステネスのふるい

アルゴリズムはウィキペディアを参考にしました。

エラトステネスの篩(Wikipedia)
https://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E7%AF%A9

数学初心者にとっても理解しやすくて、単純なところが良いですね。
コード量もこんなもん。

public static List<int> GeneratePrime(int max)
{
    System.Diagnostics.Debug.Assert(max >= 2);  // maxは2以上の数

    int prime;
    double sqrtMax = Math.Sqrt(max);
    var primeList = new List<int>();

    // ■ステップ 1
    // 探索リストに2からxまでの整数を昇順で入れる。
    var searchList = Enumerable.Range(2, max - 1).ToList();

    do
    {
        // ■ステップ 2
        // 探索リストの先頭の数を素数リストに移動し、その倍数を探索リストから篩い落とす。
        prime = searchList.First();
        // 素数リストに追加
        primeList.Add(prime);
        // 倍数をふるい落とす
        searchList.RemoveAll(n => n % prime == 0);

        // ■ステップ 3
        // 上記の篩い落とし操作を探索リストの先頭値がxの平方根に達するまで行う。
    } while (prime < sqrtMax);

    // ■ステップ 4
    // 探索リストに残った数を素数リストに移動して処理終了。
    primeList.AddRange(searchList);

    return primeList;
}

その他のアルゴリズム

世の中には他にもこういったアルゴリズムがあるらしい・・・

• Atkin（アトキン）の篩

参考にしたサイト

エラトステネスの篩
https://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E7%AF%A9
素数判定
https://ja.wikipedia.org/wiki/%E7%B4%A0%E6%95%B0%E5%88%A4%E5%AE%9A
素数判定・素数列挙を行う主なアルゴリズムをPython 3で実装してみた：試し割り法からMiller-Rabin素数判定法まで
http://hamukichi.hatenablog.jp/entry/2016/02/17/215948
PHPでエラトステネスの篩で素数判定をやってみる 『素数』を数えて落ち着くんだ…
http://tech.basicinc.jp/php/2013/08/18/php_prime_eratosthenes/