素数を求める（その2）

　 さて、「素数を求める（その１）」で、N＝100

とし、100迄の素数を求めました。その時２５個の

素数があったわけですが、Nをより大きな数字にし

たらどうなるか？を考えてみました。

N＝ 10,000の時

　素数の数：1,229個

　処理時間：  164 ms

　処理回数：  　49,985,001回

N＝ 20,000の時

　素数の数：2,262個

　処理時間：  617 ms

　処理回数：　199,970,001回

N＝ 50,000の時

　素数の数：5,133個

　処理時間： 3,468 ms

　処理回数：1,249,925,001回

N＝100,000

　素数の数：9,592個

　処理時間：14,119 ms

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

　と言うようにNが10万程度でも素数はちゃんと

拾いだせるのですが、計算ループ部分の処理回数

が50億回位になって、処理時間は14秒以上も掛

かってきます。

　

　そこで、もっと短い時間で処理できるように

プログラムの改善を考えてみます。

　ｎと言う数字が素数か調べるためにｎ-1迄の

数字で割っていますが、ｎはｎ/2以上の数字で

割っても、2以下にしかなりませんので、

n-1迄の数字ではなく、ｎ/2迄の数字で割れば

十分です。

　但し、ｎ-1⇒ｎ/2ではプログラム上ｎを整数

であるintと定義しているので、例えば3/2=1.5

でなく1、5/2=2.5でなく2となるので、念の為

にｎ-1⇒ｎ/2+1としてみます。

　変更後、処理時間及び処理回数が半分になりました。