素数を求める（その５）

 　今までに改良してきたプログラムは、素数か

どうか調べたい数字ｎをそれより小さい数字iで

割ってみて余りがあるかどうかで判定している

が、全てのiで割った後、１個以上割れる数字が

有った時に素数と判断している。

　今回はiで割る時割り切れる数字が１個見つ

かったら、すぐに次のｎを調べるようにする。

　こうすれば、素数でないと分かった後の無駄

な計算をする事を省ける。

その方法は、図のようにbreak;を入れるだけ

で済む。

　これにより、2秒かかった計算が0.5秒に

なった。「素数を求める(No.１)」のプログ

ラムからの改善の結果、

N＝100,000の時

　素数の数：9,592個

　処理時間：14,119 ms

　処理回数：4,999,850,001回

であったのが、今回の改善「素数を求める(その５)」

のプログラムでは、

N＝100,000の時

　素数の数：9,592個

　処理時間：518 ms

　処理回数：  113,970,448回

N＝1,000,000の時

　素数の数：78,498個

　処理時間：36,915 ms

　処理回数：  9,395,812,778回

にする事が出来た。

因みに、「素数を求める(No.１)」のプログラム

に、break；を入れた場合は

N＝100,000の時

　素数の数：9,592個

　処理時間：1051 ms

　処理回数：227,995,678回

N＝1,000,000の時

　素数の数：78,498個

　処理時間：77,986 ms

   処理回数：18,792,164,730回

であった。

尚、「素数を求める(No.１)」のプログラム

に、break；を入れなかった場合には

N＝1,000,000の時

　素数の数：78,498個

　処理時間：708,240 ms (約12分)

　処理回数：249,999,000,001回