Help us understand the problem. What is going on with this article?

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

More than 3 years have passed since last update.

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/

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away