素数を列挙する

プログラミングの練習。指定された範囲にある素数を列挙するプログラムを作ってみる。

素数表を使った判定

利用するアルゴリズムは自明のもの。つまり、正整数 n に対して √ n を超えない素数で割り切れるかどうかをチェックしている。初回の実行では 2 (最小の素数)から始めて素数表を作っている。実行中に作った素数表は最後にファイルに書き出す。2 回目以降の実行では、以前に作った素数表を読み込んでいる。

列挙した素数の後にカッコ付きで表示する数字は計算回数だ。

検証

念には念を入れて、listprimes.rb で作られた primes.txt を検証する。以下がそのプログラムだ。素数を判定するアルゴリズムは大して変わっていない(素数表を使わず √ n 以下の整数で割り切れるか否かをチェック)から、どちらかと言えばプログラムのバグを確認するためのものというべきだ。

実行結果

[imac] mnbi% ls primes.txt
ls: primes.txt: No such file or directory
[imac] mnbi% ./listprimes.rb 1000 50
START (2):
1009 (12)
1013 (12)
1019 (12)
1021 (12)
1031 (12)
1033 (12)
1039 (12)
1049 (12)
Elapsed: 0.00011
[imac] mnbi% tail primes.txt
991
997
1009
1013
1019
1021
1031
1033
1039
1049
[imac] mnbi% ./listprimes.rb 1000 50
START (1049):
1009 (0)
1013 (0)
1019 (0)
1021 (0)
1031 (0)
1033 (0)
1039 (0)
1049 (0)
Elapsed: 0.000444

初回の listprimes.rb の実行で、primes.txt が作られ、2 回目の実行では、(素数判定のための)計算がされていないことが(計算回数の表示から)読み取れる。意外なことに計算のない 2 回目の方が時間がかかっている。

「√ n 以下の整数」を使うより「√ n 以下の素数」の方が計算回数がぐっと少なくなると考えて素数表を使うようにしたんだが、実際のところでは素数表(配列)の操作にかかる時間の方が律速段階になっているようだ。素数表を使う方法で 2 回目以降の実行(つまり割り算は一切ない)でも、Time で計測してもわかるほどの差が出る。

素数表の検索を工夫すれば逆転するだろうか？

関連リンク

• 素数 (Wikipedia:ja)