素数を求めるプログラムを以下に示します。 BASIC言語の形式によって、若干、
記述法が違いますが、コアとなる部分は基本的に同じになるので、フリーソフトなど
を使って実際にプログラムを実行してみてください。因みに、ここでは十進BASIC
を使っています。
素数とは1と自分自身でしか割り切れない2以上の自然数です。ですから、約数の
数が2個しかない自然数を求めればよい訳です。
以下に、 上記のプログラムを使って求めた素数を示します。 2から始まって小さい
順に25個示しました。
小さい順に1000個の素数を求めるには、かなりの時間を要します。 どうすれば、
その時間を最小にできるか、自分でプログラムを工夫してみてください。
最後に、 計算時間を測定する方法を示しておきます。 INPUT文のすぐ後に、 次の
命令文を入れてください。
LET T0=TIME
そして、END文のすぐ前に、次の命令文を入れれば、計算結果とともにかかった時
間が画面上に表示されます。
PRINT TIME-T0;"秒かかりました"
実際に計算時間を測定した結果を示します。 1000より大きい最初の素数を計算
する時間が0.18秒になりました。 10000、100000、1000000そして10000
000についても結果を示したので参考にしてください。得られた計算時間から判断
すると、一億(八桁)を超える素数を求めるには半日ぐらいかかるかもしれません。
プログラムの効率化だけでなく、 使用しているコンピュータの性能、 特に、CPUの
処理スピードの評価にも時間測定は有効です。
プログラムの高速化へのヒント
素数の中で一番小さい2を除けば、残りの素数はすべて奇数になります。したがっ
て、奇数だけチェックすることを考えれば、計算時間は単純に半分になります。 さら
に、自然数は基本的に素因数分解できるので、チェックしている自然数のルートを
とって、 その数を超えないすべての素数で自然数が割り切れるかどうかを判断基
準にするというやり方もあると思います。 ただし、 この場合は配列を使って求めた
素数をすべて記憶させる必要があります。
最大素数の探索
2013年現在で、判っている最大素数は2の57885161乗−1だそうです。一億
桁以上の新たな素数を見つけると、 15万ドルの賞金がもらえるようです。 時間が
ある方は挑戦してみてください。ちなみに、十億桁以上なら、25万ドルです。
EFF Cooperative Computing Awards
素数と暗号