素数判定

　　素数判定 桜 2005/12/21 05:09:14 
　　├単純な効率化としては、2より大きい偶数で割... 青木太一 2005/12/21 09:16:10 
　　│└なるほど。ありがとうございます。ちょっと... 桜 2005/12/21 16:04:42 
　　├素因数分解のプログラムを以前作りました。... 荒田浩二 2005/12/23 16:27:35 
　　└素数判定 河川屋 2005/12/30 11:17:54

　　素数判定 桜 2005/12/21 05:09:14  ツリーへ

素数判定 返事を書く

桜 2005/12/21 05:09:14

どうも今晩は。またよろしくお願いします。さて、次のプログラムは、素数判定ですが、どなたか、さらに改良していただけないでしょうか。コンピュータの計算の負担を減らして、短時間にそして効率よく処理したいのです。よろしくお願いします。
　input s　
for i=2 to sqr(s)
if mod (s,i)=0 then 100
next i
print "is a prime"
goto 100
100 print "is not prime"
print i;
print "is a divisor"

以前投稿して、回答をもらいました。今回のとはまったく異なる話だったのですが、いまだにうまくいきません。怠けているからなのですが、きっとうまくいったらここに書きます。

　　├単純な効率化としては、2より大きい偶数で割... 青木太一 2005/12/21 09:16:10  ツリーへ

Re: 素数判定 返事を書く

青木太一 2005/12/21 09:16:10

単純な効率化としては、2より大きい偶数で割れるかどうかの判定は必要ないので、for文のstepを2とするのが思いつきます。

なお、桜さんの書いたプログラムはprint "is prime"のあとにstopを置かないと、表示が変じゃないですか？
あと、行番号100の直前のgoto 100は不要だと思います。
たとえば7を入力すると以下のようになります。

? 7
is a prime
is not prime
3 is a divisor

まあ is a primeと出力されたら、後ろの行は無視すると人間が判断すれば問題ありませんが。

そのうえで、偶数の判定を改良したプログラムは以下の通りです。

input s
if mod(2,s)=0 then 100
for i=3 to sqr(s) step 2
if mod (s,i)=0 then 100
next i
print "is a prime"
stop
goto 100
100 print "is not prime"
print i;
print "is a divisor"
print s/i
END

なお、Googleで「素数判定」を検索すると、より高度なアルゴリズムもあるようですが、私にはよくわかりませんでした。

　　│└なるほど。ありがとうございます。ちょっと... 桜 2005/12/21 16:04:42  ツリーへ

Re: 単純な効率化としては、2より大きい偶数で割... 返事を書く

桜 2005/12/21 16:04:42

なるほど。ありがとうございます。ちょっとした手直しのレベルさえ、まだ、私には、少しだけ面倒なようです。私が書きたかったプログラムは、ちなみに、
input s
for i=2 to sqr(s)
if mod (s,i)=0 then 100
next i
print "is a prime"
goto 200
100 print "is not prime"
print i;
print "is a divisor"
200 END
でした。

　　├素因数分解のプログラムを以前作りました。... 荒田浩二 2005/12/23 16:27:35  ツリーへ

Re: 素数判定 返事を書く

荒田浩二 2005/12/23 16:27:35

素因数分解のプログラムを以前作りました。参考にしていただければと思います。
ただし、素数判定用の配列ｃが大きいので、コンピュータへの負担は数値が大きくなると相当のものがあります。入力できる数値はメモリーの容量に依存し、１ＧＢで10の14乗くらいが限度でしょう。
コンピュータへ負担をかけないということならば、あらかじめ必要な数までの素数列をファイルに作っておいて、実行時にファイルから読み出すという方法があります。メモリーはほとんど消費しません。何度も実行されるのならば、これがベストでしょう。
参考までに、10の7乗までに素数は664,579個ありファイルの大きさは約7000Ｋバイトになります。これで10の14乗までの素数を判定できます。

REM *** 素因数分解 ***
OPTION ARITHMETIC NATIVE
INPUT n
IF n<>INT(n) OR n<=1 THEN
PRINT "The data is out of range! stop!!"
STOP
END IF
DIM pf(50) ! 素因数(最大50個)
LET k=0 ! 素因数の個数
LET q=n ! qは、商
LET m=1 ! 検証用変数
LET sn=CEIL(SQR(n)/2)+1
DIM c(sn) ! 素数判定用配列(奇数のみ判定する)
MAT c=ZER
LET c(1)=1 ! 合成数は、1 (便宜上1を合成数とする)
LET c(2)=0 ! 素数は、0 (3が素数であることを示す)
CALL factor(2) ! 素数2が因数となるか検査
SUB factor(d) ! 因数を判定する副プログラム
DO WHILE MOD(q,d)=0
LET k=k+1
LET pf(k)=d ! dはnの因数
LET m=m*d
LET q=q/d
LOOP
END SUB
LET dv=3 ! 素数3から2きざみで検査をはじめる
DO WHILE dv<=SQR(q)
DO WHILE c((dv+1)/2)=1 ! 素数判定ルーチン
LET dv=dv+2
LOOP
CALL factor(dv) ! dvが素数のときfactorを呼び出す
IF q=1 THEN EXIT DO
FOR i=(dv+1)/2+dv TO CEIL(SQR(q)/2) STEP dv !エラトステネスのふるい
LET c(i)=1 ! dvの倍数(奇数倍)にチェックを入れる
NEXT i
LET dv=dv+2
LOOP
REM ** 出力 **
IF q=n OR n=2 THEN
PRINT n;"=";n;" [素数]"
ELSE
PRINT n;"=";pf(1);
FOR j=2 TO k
PRINT "*";pf(j);
NEXT j
IF q<>1 THEN
PRINT"*";q;
LET m=m*q
END IF
IF m<>n THEN PRINT "error !!!"
PRINT
END IF
END

　　└素数判定 河川屋 2005/12/30 11:17:54  ツリーへ

Re: 素数判定 返事を書く

河川屋 2005/12/30 11:17:54

素数判定
>短時間にそして効率よく処理したい
フェルマーの小定理を使います。
フェルマーの小定理:
「整数aが素数pの倍数でなければ，a^p-1はpで割り切れる。」
よって、pが素数かどうか知りたい場合、
a^p-1を計算して、ｐで割りきれるかどうかを調べます。
(割りきれない場合、素数でないことが確定。)
例:10が素数かどうか?
2^10-1=1022 mod(1022,10)=3 よって割りきれないので素数ではない。
この方法の欠点として、aをただ1つ(たとえば2)調べただけでは、
素数でないのに素数と判定されてしまうことがありうる点。
だから、aは2,3,5...と調べていかないとならないけど、
適当なところ(√pより充分小さいところ)で打ち止めしてもめったにミスりません。
よって、「√pより小さい奇数で順次割る」という方法より
速い方法です。ただし、「剰余系における整数の冪の高速計算法」
を知っていないと、どうしようもないのですが。

インデックスへ EXIT
新規発言を反映させるにはブラウザの更新ボタンを押してください。

素数判定	返事を書く
桜 2005/12/21 05:09:14
どうも今晩は。またよろしくお願いします。さて、次のプログラムは、素数判定ですが、どなたか、さらに改良していただけないでしょうか。コンピュータの計算の負担を減らして、短時間にそして効率よく処理したいのです。よろしくお願いします。　input s　 for i=2 to sqr(s) if mod (s,i)=0 then 100 next i print "is a prime" goto 100 100 print "is not prime" print i; print "is a divisor" 以前投稿して、回答をもらいました。今回のとはまったく異なる話だったのですが、いまだにうまくいきません。怠けているからなのですが、きっとうまくいったらここに書きます。

Re: 素数判定	返事を書く
青木太一 2005/12/21 09:16:10
単純な効率化としては、2より大きい偶数で割れるかどうかの判定は必要ないので、for文のstepを2とするのが思いつきます。なお、桜さんの書いたプログラムはprint "is prime"のあとにstopを置かないと、表示が変じゃないですか？あと、行番号100の直前のgoto 100は不要だと思います。たとえば7を入力すると以下のようになります。 ? 7 is a prime is not prime 3 is a divisor まあ is a primeと出力されたら、後ろの行は無視すると人間が判断すれば問題ありませんが。そのうえで、偶数の判定を改良したプログラムは以下の通りです。 input s if mod(2,s)=0 then 100 for i=3 to sqr(s) step 2 if mod (s,i)=0 then 100 next i print "is a prime" stop goto 100 100 print "is not prime" print i; print "is a divisor" print s/i END なお、Googleで「素数判定」を検索すると、より高度なアルゴリズムもあるようですが、私にはよくわかりませんでした。

Re: 単純な効率化としては、2より大きい偶数で割...	返事を書く
桜 2005/12/21 16:04:42
なるほど。ありがとうございます。ちょっとした手直しのレベルさえ、まだ、私には、少しだけ面倒なようです。私が書きたかったプログラムは、ちなみに、 input s for i=2 to sqr(s) if mod (s,i)=0 then 100 next i print "is a prime" goto 200 100 print "is not prime" print i; print "is a divisor" 200 END でした。

Re: 素数判定	返事を書く
荒田浩二 2005/12/23 16:27:35
素因数分解のプログラムを以前作りました。参考にしていただければと思います。ただし、素数判定用の配列ｃが大きいので、コンピュータへの負担は数値が大きくなると相当のものがあります。入力できる数値はメモリーの容量に依存し、１ＧＢで10の14乗くらいが限度でしょう。コンピュータへ負担をかけないということならば、あらかじめ必要な数までの素数列をファイルに作っておいて、実行時にファイルから読み出すという方法があります。メモリーはほとんど消費しません。何度も実行されるのならば、これがベストでしょう。参考までに、10の7乗までに素数は664,579個ありファイルの大きさは約7000Ｋバイトになります。これで10の14乗までの素数を判定できます。 REM * 素因数分解 * OPTION ARITHMETIC NATIVE INPUT n IF n<>INT(n) OR n<=1 THEN PRINT "The data is out of range! stop!!" STOP END IF DIM pf(50) ! 素因数(最大50個) LET k=0 ! 素因数の個数 LET q=n ! qは、商 LET m=1 ! 検証用変数 LET sn=CEIL(SQR(n)/2)+1 DIM c(sn) ! 素数判定用配列(奇数のみ判定する) MAT c=ZER LET c(1)=1 ! 合成数は、1 (便宜上1を合成数とする) LET c(2)=0 ! 素数は、0 (3が素数であることを示す) CALL factor(2) ! 素数2が因数となるか検査 SUB factor(d) ! 因数を判定する副プログラム DO WHILE MOD(q,d)=0 LET k=k+1 LET pf(k)=d ! dはnの因数 LET m=md LET q=q/d LOOP END SUB LET dv=3 ! 素数3から2きざみで検査をはじめる DO WHILE dv<=SQR(q) DO WHILE c((dv+1)/2)=1 ! 素数判定ルーチン LET dv=dv+2 LOOP CALL factor(dv) ! dvが素数のときfactorを呼び出す IF q=1 THEN EXIT DO FOR i=(dv+1)/2+dv TO CEIL(SQR(q)/2) STEP dv !エラトステネスのふるい LET c(i)=1 ! dvの倍数(奇数倍)にチェックを入れる NEXT i LET dv=dv+2 LOOP REM * 出力 ** IF q=n OR n=2 THEN PRINT n;"=";n;" [素数]" ELSE PRINT n;"=";pf(1); FOR j=2 TO k PRINT "";pf(j); NEXT j IF q<>1 THEN PRINT"";q; LET m=m*q END IF IF m<>n THEN PRINT "error !!!" PRINT END IF END

Re: 素数判定	返事を書く
河川屋 2005/12/30 11:17:54
素数判定 >短時間にそして効率よく処理したいフェルマーの小定理を使います。フェルマーの小定理: 「整数aが素数pの倍数でなければ，a^p-1はpで割り切れる。」よって、pが素数かどうか知りたい場合、 a^p-1を計算して、ｐで割りきれるかどうかを調べます。 (割りきれない場合、素数でないことが確定。) 例:10が素数かどうか? 2^10-1=1022 mod(1022,10)=3 よって割りきれないので素数ではない。この方法の欠点として、aをただ1つ(たとえば2)調べただけでは、素数でないのに素数と判定されてしまうことがありうる点。だから、aは2,3,5...と調べていかないとならないけど、適当なところ(√pより充分小さいところ)で打ち止めしてもめったにミスりません。よって、「√pより小さい奇数で順次割る」という方法より速い方法です。ただし、「剰余系における整数の冪の高速計算法」を知っていないと、どうしようもないのですが。