素数判定

 投稿者：しばっち  投稿日：2015年10月 9日(金)22時46分54秒
  https://ja.wikipedia.org/wiki/ミラー?ラビン素数判定法

!'素数判定　Miller-Rabin法
OPTION ARITHMETIC RATIONAL
LET L=100000000000000 !'100兆
FOR N=L+1 TO L+10001 STEP 2
   IF ISPRIME(N)=1 THEN
   !'PRINT N
      LET COUNT=COUNT+1
   END IF
NEXT N
PRINT COUNT;"個"
END

EXTERNAL  FUNCTION ISPRIME(N)
OPTION ARITHMETIC RATIONAL
IF N = 2 THEN
   LET ISPRIME=1
   EXIT FUNCTION
END IF
IF N = 1 OR MOD(N , 2) = 0 THEN
   LET ISPRIME=0
   EXIT FUNCTION
END IF
LET D = (N - 1) / 2
LET S = 0
DO WHILE MOD(D , 2) = 0
   LET D = INT(D / 2)
   LET S=S+1
LOOP
FOR I=1 TO 10
   LET ISP=0
   READ A    !' n < 341550071728321 なら a = 2, 3, 5, 7, 11, 13, 17
   DATA 2,3,5,7,11,13,17,23,29,31
   LET ISP = 0
   LET R = POWMOD(A, D, N)
   IF R = 1 OR R = N - 1 THEN
      LET ISP = 1
   END IF
   LET R = POWMOD(R, 2, N)
   FOR J = 0 TO S-1
      IF R = N - 1 THEN
         LET ISP = 1
      END IF
      LET R = POWMOD(R, 2, N)
   NEXT J
   IF ISP=0 THEN
      LET ISPRIME=0
      EXIT FUNCTION
   END IF
NEXT I
LET ISPRIME=1
END FUNCTION

EXTERNAL  FUNCTION POWMOD(B,P,M)
OPTION ARITHMETIC RATIONAL
LET RESULT = 1
DO WHILE P > 0
   IF MOD(P , 2)= 1 THEN
      LET RESULT = MOD(RESULT * B , M)
   END IF
   LET B = MOD(B * B, M)
   LET P = INT(P / 2)
LOOP
LET POWMOD=RESULT
END FUNCTION
 		 

Re: 素数判定

 投稿者：たろさ  投稿日：2015年10月10日(土)08時31分11秒
  しばっちさんへのお返事です。

素数100万個刻みのリストを作成しています。

素数個数関数と合わせて便利に使用させて頂いてます。

素数個数関数30億までの計算中ですが

処理速度の変化は、はじめてなのでわかりません。

素数個数関数の30億の計算は予想した約60時間で終わりそうです。

http://blogs.yahoo.co.jp/donald_stinger

  

Re: 素数判定

 投稿者：たろさ  投稿日：2016年 4月26日(火)18時13分41秒
  > No.3894[元記事へ]

しばっちさんへのお返事です。

お世話になります。

OPTION ARITHMETIC RATIONAL     !有理数モード
LET t0=TIME
FOR n=1 TO 1279
   LET m=2^n-1
   IF ISPRIME(m)=1 THEN PRINT n;m
NEXT n
PRINT TIME-t0;"秒で計算しました"
END

EXTERNAL FUNCTION ISPRIME(N)
OPTION ARITHMETIC RATIONAL     !有理数モード
IF N=2 OR N=3 OR N=5 OR N=7 OR N=11 OR N=13 OR N=17 OR N=19 OR N=23 OR N=29 OR N=31 THEN
   LET ISPRIME=1
   EXIT FUNCTION
END IF

IF N=1 OR MOD(N,2)=0 THEN
   LET ISPRIME=0
   EXIT FUNCTION
END IF
LET D=(N-1)/2
LET S=0
DO WHILE MOD(D,2)=0
   LET D=INT(D/2)
   LET S=S+1
LOOP
FOR I=1 TO 11
   LET ISP=0
   READ A    !' n < 341550071728321 なら a = 2, 3, 5, 7, 11, 13, 17
   DATA 2,3,5,7,11,13,17,19,23,29,31
   LET ISP=0
   LET R=POWMOD(A, D, N)
   IF R=1 OR R=N-1 THEN
      LET ISP=1
   END IF
   LET R=POWMOD(R, 2, N)
   FOR J=0 TO S-1
      IF R=N-1 THEN
         LET ISP=1
      END IF
      LET R=POWMOD(R, 2, N)
   NEXT J
   IF ISP=0 THEN
      LET ISPRIME=0
      EXIT FUNCTION
   END IF
NEXT I
LET ISPRIME=1
END FUNCTION

EXTERNAL  FUNCTION POWMOD(B,P,M)
OPTION ARITHMETIC RATIONAL     !有理数モード
LET RESULT=1
DO WHILE P>0
   IF MOD(P,2)=1 THEN
      LET RESULT=MOD(RESULT*B,M)
   END IF
   LET B=MOD(B*B,M)
   LET P=INT(P/2)
LOOP
LET POWMOD=RESULT
END FUNCTION


----------------------
計算結果

2  3
3  7
7  127
13  8191
17  131071
19  524287
31  2147483647
61  2305843009213693951
89  618970019642690137449562111
107  162259276829213363391578010288127
127  170141183460469231731687303715884105727
521  6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151
607  531137992816767098689588206552468627329593117727031923199444138200403559860852242739162502265229285668889329486246501015346579337652707239409519978766587351943831270835393219031728127
1279  10407932194664399081925240327364085538615262247266704805319112350403608059673360298012239441732324184842421613954281007791383566248323464908139906605677320762924129509389220345773183349661583550472959420547689811211693677147548478866962501384438260291732348885311160828538416585028255604666224831890918801847068222203140521026698435488732958028878050869736186900714720710555703168729087


2(1st prime)
3(2nd prime)
7(4th prime)
13(6th prime)
17(7th prime)
19(8th prime)
31(11th prime)
61(18th prime)
89(24th prime)
107(28th prime)
127(31st prime)
521(98th prime)
607(111th prime)
1279(207th prime)
2203(328th prime)
2281(339th prime)
3217(455th prime)
4253(583rd prime)
4423(602nd prime)

n=6000まで 確認しました。ずーっと続くといいのですが ?

LET=190797007524439073807468042969529173669356994749940177394741882673528979787005053706368049835514900244303495954950709725762186311224148828811920216904542206960744666169364221195289538436845390250168663932838805192055137154390912666527533007309292687539092257043362517857366624699975402375462954490293259233303137330643531556539739921926201438606439020075174723029056838272505051571967594608350063404495977660656269020823960825567012344189908927956646011998057988548630107637380993519826582389781888135705408653045219655801758081251164080554609057468028203308718724654081055323215860189611391296030471108443146745671967766308925858547271507311563765171008318248647110097614890313562856541784154881743146033909602737947385055355960331855614540900081456378659068370317267696980001187750995491090350108417050917991562167972281070161305972518044872048331306383715094854938415738549894606070722584737978176686422134354526989443028353644037187375385397838259511833166416134323695660367676897722287918773420968982326089026150031515424165462111337527431154890666327374921446276833564519776797633875503548665093914556482031482248883127023777039667707976559857333357013727342079099064400455741830654320379350833236245819348824064783585692924881021978332974949906122664421376034687815350484991

エラーが出ます。1000桁超えると有理数モードでも代数として認識しないのでしょうか?

どうしたらいいですか?  教えてください。

mの素数判定　3217(455th prime)　までは別programでも、素数の確率が高いと出てます。

http://blogs.yahoo.co.jp/donald_stinger

  

Re: 素数判定

 投稿者：たろさ  投稿日：2021年 6月11日(金)18時12分12秒
  > No.3894[元記事へ]

しばっちさんへのお返事です。

> https://ja.wikipedia.org/wiki/ミラー?ラビン素数判定法
>
> !'素数判定　Miller-Rabin法
> OPTION ARITHMETIC RATIONAL
> LET L=100000000000000 !'100兆
> FOR N=L+1 TO L+10001 STEP 2
>    IF ISPRIME(N)=1 THEN
>    !'PRINT N
>       LET COUNT=COUNT+1
>    END IF
> NEXT N
> PRINT COUNT;"個"
> END
>
> EXTERNAL  FUNCTION ISPRIME(N)
> OPTION ARITHMETIC RATIONAL
> IF N = 2 THEN
>    LET ISPRIME=1
>    EXIT FUNCTION
> END IF
> IF N = 1 OR MOD(N , 2) = 0 THEN
>    LET ISPRIME=0
>    EXIT FUNCTION
> END IF
> LET D = (N - 1) / 2
> LET S = 0
> DO WHILE MOD(D , 2) = 0
>    LET D = INT(D / 2)
>    LET S=S+1
> LOOP
> FOR I=1 TO 10
>    LET ISP=0
>    READ A    !' n < 341550071728321 なら a = 2, 3, 5, 7, 11, 13, 17
>    DATA 2,3,5,7,11,13,17,23,29,31
>    LET ISP = 0
>    LET R = POWMOD(A, D, N)
>    IF R = 1 OR R = N - 1 THEN
>       LET ISP = 1
>    END IF
>    LET R = POWMOD(R, 2, N)
>    FOR J = 0 TO S-1
>       IF R = N - 1 THEN
>          LET ISP = 1
>       END IF
>       LET R = POWMOD(R, 2, N)
>    NEXT J
>    IF ISP=0 THEN
>       LET ISPRIME=0
>       EXIT FUNCTION
>    END IF
> NEXT I
> LET ISPRIME=1
> END FUNCTION
>
> EXTERNAL  FUNCTION POWMOD(B,P,M)
> OPTION ARITHMETIC RATIONAL
> LET RESULT = 1
> DO WHILE P > 0
>    IF MOD(P , 2)= 1 THEN
>       LET RESULT = MOD(RESULT * B , M)
>    END IF
>    LET B = MOD(B * B, M)
>    LET P = INT(P / 2)
> LOOP
> LET POWMOD=RESULT
> END FUNCTION
>

素数判定の実験中遭遇しました。
十進BASIC Version 7.8.5.4　　　　　計算結果　11
BASIC Accelerator Ver. 2.0.2.0　　　計算結果　10
BASIC Accelerator Ver. 1.2.0.5　　　計算結果　10

それぞれ計算結果が違います。

!OPTION ARITHMETIC RATIONAL
PRINT  ISPRIME(94910593) !94910593 素数 (5484840th)
PRINT  ISPRIME(94910639) !94910639 素数 (5484841st)
END

EXTERNAL  FUNCTION ISPRIME(N)
!OPTION ARITHMETIC RATIONAL
IF N = 2 THEN
   LET ISPRIME=1
   EXIT FUNCTION
END IF
IF N = 1 OR MOD(N , 2) = 0 THEN
   LET ISPRIME=0
   EXIT FUNCTION
END IF
LET D = (N - 1) / 2
LET S = 0
DO WHILE MOD(D , 2) = 0
   LET D = INT(D / 2)
   LET S=S+1
LOOP
FOR I=1 TO 10
   LET ISP=0
   READ A    !' n < 341550071728321 なら a = 2, 3, 5, 7, 11, 13, 17
   DATA 2,3,5,7,11,13,17,23,29,31
   LET ISP = 0
   LET R = POWMOD(A, D, N)
   IF R = 1 OR R = N - 1 THEN
      LET ISP = 1
   END IF
   LET R = POWMOD(R, 2, N)
   FOR J = 0 TO S-1
      IF R = N - 1 THEN
         LET ISP = 1
      END IF
      LET R = POWMOD(R, 2, N)
   NEXT J
   IF ISP=0 THEN
      LET ISPRIME=0
      EXIT FUNCTION
   END IF
NEXT I
LET ISPRIME=1
END FUNCTION

EXTERNAL  FUNCTION POWMOD(B,P,M)
!OPTION ARITHMETIC RATIONAL
LET RESULT = 1
DO WHILE P > 0
   IF MOD(P , 2)= 1 THEN
      LET RESULT = MOD(RESULT * B , M)
   END IF
   LET B = MOD(B * B, M)
   LET P = INT(P / 2)
LOOP
LET POWMOD=RESULT
END FUNCTION
 

戻る