こんにちはゲストさん。会員登録(無料)して質問・回答してみよう!

解決済みの質問

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
10continue
do 20 i=2,50000000
if(table(i).eq.0)then
cnt=cnt+1
end if
20continue
write(6,610)cnt
610format('sosu no goukei =',i8)
end

投稿日時 - 2007-11-01 22:24:55

QNo.3481443

困ってます

質問者が選んだベストアンサー

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

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クリアされていることが多いですが、こういうのに頼ってはいけません。

投稿日時 - 2007-11-01 23:03:44

お礼

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

投稿日時 - 2007-11-02 00:26:46

ANo.1

このQ&Aは役に立ちましたか?

0人が「このQ&Aが役に立った」と投票しています

回答(1)

あなたにオススメの質問