fortran 途中まで考えたのですが。。。。

質問

エラトステネスのふるい（素数の倍数を除いていって残ったのが素数）で３桁の素数を求めて表示したいです。
私が考えたのは、
１・２～９９までの数を素数かどうか調べて、素数を配列に入れていく
２・１００～９９９まで素数の配列の中の数で割って、割り切れたらおしまい。割り切れなかったら表示していく

ということです。
しかし下のプログラムではうまく素数配列ができていないようなのです。
ここまでかなり時間がかかったのでこのプログラムに手をいれて
これ以外におかしくなるところもどこを直せばいいのか教えてくださるとうれしいです。

C
C q223.f
C
PROGRAM q223
C
IMPLICIT NONE
C
INTEGER N,i,K,s,l
REAL a(99),b(99),c(99),X,Y
C
real M
C
a(1)=2
a(2)=3
l=2
C

DO N=2,99,1
M=N**(0.5)
S=M
DO i=2,S,1
K=MOD(N,i)
IF(K ==0)THEN
exit
ELSE IF(K /=0)THEN
l=l+1
a(l)=N
ENDIF
ENDDO
ENDDO
C
do N=100,999
do l=1,99
X=a(l)
Y=N/X
if(Y==0)then
exit
else if(Y/=0)then
write(*,*)N
end if
end do
end do
c
end

よろしくおねがいします

回答No.3

kmee · ベストアンサー

> １・２～９９までの数を素数かどうか調べて、素数を配列に入れていく
> ２・１００～９９９まで素数の配列の中の数で割って、割り切れたらおしまい。割り切れなかったら表示していく

「素数を求める」という問題ならこの方法でも間違いではないですが、「エラトステネスのふるい」を使いたいなら、まったく違います。
時間がかかったのでもったいない、という気持ちもわからなくはないですが、「これを直」すより、最初から作りなおした方が早いです。

以下は「ふるい」ではないので、余談となります。

素数判定がうまくいかないのは、判定方法のロジックミスです。
>IF(K ==0)THEN
>exit
>ELSE IF(K /=0)THEN
>l=l+1
>a(l)=N
>ENDIF
ですが、K==0(=割り切れた)らループ終了、はいいとして
そうでない場合、他の素数では割り切れる可能性があるのに素数と判定してしまっています。
具体例では
・15は素数ではありません
・ √5≒3.8... なので、S=3
・i=2で 15 ÷ 2 = 7あまり1なので、 K=1
・K==0でないのでELSE節へ
・K/=0なので、THEN以降を実行→15を「素数」と判定
となります。このように、2で割り切れなければ、全て「素数」と判定されます。
ようは「奇数判定プログラム」になっています。

「DO i=2,S,1 のすべてのiについて割り切れなかった」場合が素数です。プログラムもそういう意味になるように作ります。
例えば、
p=0
DO i=2,S,1
..
IF K==0 THEN
p=1
exit
ENDIF
ENDDO
IF P==0 THEN 素数
とかのように、途中で割り切れたらフラグを立てる、等です。

後半も判定については同様。さらに
>do l=1,99
>X=a(l)
>Y=N/X
(前半が正しければ) aには2～99までの素数が入っているはずなので、その個数は99ではありません。
個数を越えたところでは、a(l)は初期値のままですから、N/Xの計算もおかしくなります。そもそも、前半ではmodであまりを求めているのに、なぜここではただの割り算になっているのでしょうか?

素数の数は、前半では変数lに入っていましたが、ここでループカウンタに使ってしまったので、もうわかりません。
do i=1,l
X=a(i)
にすれば、判明している素数だけが使われます。

さらに余談ですが(ELSE以降をループの外に出すので、今回のプログラムでは以下の分は使わない)
> IF(K ==0)THEN
..
> ELSE IF(K /=0)THEN
K==0でないなら、必ずK /=0 です。
ELSEに来る、ということは、K==0ではありません。よって、IF (K/=0)というのは必ず THENを実行します。
こういう場合は
IF(K ==0)THEN
..
ELSE
で十分です。

お礼

たしかに！！！

全く変なプログラムになっていますね・・・・
ちなみにエラトステネスのふるいをつくるとどうなるのでしょうか？？
教えてください！！！

回答No.4

40000Km

エラトステネスのふるいのアルゴリズム

まず１０００個の配列を用意します（整数型）
すべて１の要素には１それ以外の要素に０をセットしておきます
次に２から配列の内容を調べて行きます
配列のｉ番目が０のときｉの２倍、３倍・・・の要素に１をセットします。ｉの倍数が１０００を超えるまで繰り返します。

ｉが１０００に到達したら完了
配列の要素で０のものが素数

お礼

エラトステネスのふるいのふるいの原理はわかりました。
ありがとうございます。

ただ上の文章をプログラムにするだけの能力がありません・・・・

回答No.2

Tacosan

「うまく素数配列ができていないよう」と思うなら, 自分で確かめればいいのでは? その結果を見て考えるものではないのですか?

お礼

それができないから聞いているのです。
わざわざ出来ることを質問するようなことはしません

回答No.1

LOHA

パッと見ですが、
IF(K ==0)THEN
　exit
ELSE IF(K /=0)THEN
　l=l+1
　a(l)=N
ENDIF
だと「割り切れるのが1個でもあったら」というのが表現できていないので、
割れないか = TRUE
DO
　IF(K == 0) THEN
　　割れないか = FALSE
　　exit
　ENDIF
END DO
IF (割れないか) THEN
　配列に入れる
END IF
のようにしないとダメかと思います。

ほんとパッと見なので間違ってたらスミマセン。

お礼

ありがとうございました