以前社内での会話の流れで「素数を列挙するプログラミングってどう書くの？」と言われた。
そこで、その場で書いて見せた。
static void Main(string[] args) {
for(var i = 0; i < 20; ++i) {
if (IsPrimeNumber(i)) Console.WriteLine(i);
}
Console.ReadKey();
}
static bool IsPrimeNumber(int value) {
if (value < 2) return false;
for(var i = 2; i <= value / 2; ++ i) {
if (value % i == 0) return false;
}
return true;
}
上記のコードを見てもらえば一目瞭然だとは思うけれど、僕は数学が苦手だ。
「これって、どういう計算しているの？」と聞かれたので、
「単純に総当たりで剰余が出たら素数じゃないと判定している」と言うと、
「エラトステネスのふるい」という方法を教わった。
１．ある数字までの表を作る
２．そこから偶数を除外する
３．残った数値を昇順に順次取り出して、その数値の倍数を除外する
４．ただし、３を実行するのは、取り出した数が調べたい数の平方根になるまでで良い
確か「偶数は素数ではないので奇数のみが判定の対象」で「素数の倍数は素数ではない」という点から、この条件に一致するものを除外するということだったかと。
で、先日ちょっと暇があったり、出水氏の以下のエントリで思い出したりしたので、自分で書いてみた。
http://blogs.wankuma.com/izmktr/archive/2008/10/01/157895.aspx
static void Main(string[] args)
{
var t = エラトステネスのふるい(20);
Console.WriteLine("おっす、オラ素数！"); // 本当は、これが言いたかっただけ
for(var i = 0; i < t.Length; ++i) {
if (!t[i]) Console.WriteLine(i);
}
Console.ReadKey();
}
static bool[] エラトステネスのふるい(int max) {
var n = new bool[max];
n[0] = n[1] = true;
for(var i = 4; i < n.Length; i += 2) n[i] = true;
for(var i = 3; i * i < max; ++i) {
if (!n[i]) for(var j = i; j < max / i; j += 2) n[i * j] = true;
}
return n;
}
実行結果は、以下の通り・・・
おっす、オラ素数！
2
3
5
7
11
13
17
19
何も考えずに書いてみたので、メモリの大きさにかなり依存する。
もう少し改良したいけど・・・