Fortranの素数のプログラム

質問

5000万までの素数を求めるプログラムなのですが、私の作ったプログラムは実行時間26秒くらいかかります。
先生が言うには10秒台が出るとのことですが、私は頑張っても時間を短くすることができません。
下に私の作ったプログラムを載せますので短くする方法を教えて下さい。
integer table(2:50000000),pno(50000000),cnt,m,i,j
m=sqrt(50000000.)
do 10 i=2,m
do 10 j=i*2,50000000,i
table(j)=1
10 continue
do 20 i=2,50000000
if(table(i).eq.0)then
cnt=cnt+1
end if
20 continue
write(6,610)cnt
610 format('sosu no goukei =',i8)
end

回答No.1

ultraCS · ベストアンサー

ちょっといじってみました。

integer table(2:50000000) / 499999999*0 /
integer cnt / 49999999 /
integer m
integer i, j

m=int(sqrt(50000000.))+1
do 20 i=2,m
if(i .gt. 2 .and. mod(i,2) .eq. 0 ) go to 20
if(i .gt. 3 .and. mod(i,3) .eq. 0 ) go to 20
if(i .gt. 5 .and. mod(i,5) .eq. 0 ) go to 20
if(i .gt. 7 .and. mod(i,5) .eq. 0 ) go to 20
do 10 j=i*2,50000000,i
if(table(j) .eq. 0) then
　table(j)=1
　cnt=cnt-1
endif
10 continue
20 continue

m=2を判定すれば偶数はすべてチェック完了でしょ。4や6のループは不要で、これだけで計算量は半減です。ついでに3や5、7位まではやっておきましょう。
then～endif構文を使うと煩雑なのでgotoにしてあります。

と思っていたら、もっとスマートなのが

do 20 i=2,m
(table(i) .eq. 0) then
　do 10 j=i*2,50000000,i
　if(table(j) .eq. 0) then
　　table(j)=1
　　cnt=cnt-1
　endif
10 continue
endif
20 continue

こちらはどうしてうまくいくか考えてみてね

あと、まず変数はdata文や宣言文で初期化しましょう。
FORTRANの言語仕様では宣言だけした変数の値は不定で、処理系に依存します。実際は0クリアされていることが多いですが、こういうのに頼ってはいけません。

お礼

4や6のループは不要というのでわかりました。
私はk=i-(i/2)*2を使って、2以外の偶数を省くというやり方でやりました。
そしたら13秒とかなり早くなりました。
ありがとうございました。