Edited at

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

More than 1 year has 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/