新しい?素数判定

 投稿者：たろさ  投稿日：2016年 4月28日(木)03時09分16秒
 
π(x) の公式　からCOS(PI*(Fact(n-1)+1)/n)　を抜き取り
nが素数の時-1となりました。

この数式を10進BASICに合わせてみました。

!素数判定
OPTION ARITHMETIC RATIONAL     !有理数モード
LET t0=TIME
FOR n=1 TO 10000 STEP 2
   LET m=(LFact(n-1)+1)/n
   IF INT(m)=m  THEN PRINT n!;":";m
NEXT n
PRINT TIME-t0;"秒"
END

EXTERNAL FUNCTION LFact(x)     !階乗
OPTION ARITHMETIC RATIONAL     !有理数モード
LET z=1
FOR n=1 TO x
   LET m=n*z
   LET z=m
   LET LFact=m
NEXT n
END FUNCTION

計算時間はAMD Athlon 64 3800+ (2.4GHz) Win8.1 32bt (16分41.41秒)

計算時間では使い物になりませんが

COS(PI*(Fact(n-1)+1)/n)=e^(i*pi)

この式の探究の役にはたつのではないでしょうか?

((n-1)!+1)/n 割り切れたら素数です。まだ10000までの確認です。

この後メモリー限界まで行ってみます。

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

  

Re: 新しい?素数判定

 投稿者：しばっち  投稿日：2016年 4月29日(金)21時08分26秒
  > No.4046[元記事へ]

たろささんへのお返事です。

> !素数判定
> OPTION ARITHMETIC RATIONAL     !有理数モード
> LET t0=TIME
> FOR n=1 TO 10000 STEP 2
>    LET m=(LFact(n-1)+1)/n
>    IF INT(m)=m  THEN PRINT n!;":";m
> NEXT n
> PRINT TIME-t0;"秒"
> END
>
> EXTERNAL FUNCTION LFact(x)     !階乗
> OPTION ARITHMETIC RATIONAL     !有理数モード
> LET z=1
> FOR n=1 TO x
>    LET m=n*z
>    LET z=m
>    LET LFact=m
> NEXT n
> END FUNCTION

階乗の計算を展開してやると計算が速くなります

OPTION ARITHMETIC RATIONAL
LET A=1
FOR N=3 TO 10000 STEP 2
   LET A=A*(N-1)*(N-2)
   LET M=(A+1)/N
   IF INT(M)=M  THEN PRINT N
NEXT N
END
 		 

Re: 新しい?素数判定

 投稿者：たろさ  投稿日：2016年 4月30日(土)23時31分10秒
  > No.4047[元記事へ]

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


> 階乗の計算を展開してやると計算が速くなります


!ウィルソンの定理を使用した素数判定
OPTION ARITHMETIC RATIONAL
LET t0=TIME
LET A=1
FOR N=3 TO 100000 STEP 2
   LET A=A*(N-1)*(N-2)
   LET M=(A+1)/N
   IF INT(M)=M  THEN PRINT N
NEXT N
PRINT TIME-t0;"秒"
END
------------------------

AMD Athlon 64 3800+ (2.4GHz) 4分05.88秒

ありがとうございます。

何桁になるのか?

高精度計算サイト50桁では、100000!

2.8242294079603478742934215780245355184774949E+456573

でした。今後が楽しみです。

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

  

Re: 新しい?素数判定

 投稿者：たろさ  投稿日：2016年 9月21日(水)18時26分8秒
  > No.4048[元記事へ]

!新しい素数判定
OPTION ARITHMETIC RATIONAL　　 !有理数モード
PRINT "k=1"
LET count=2
LET f=2
FOR n=2 TO 3^2-1
   LET z=n/f
   !PRINT n;":";z
   IF n=NUMER(z) THEN
      PRINT count;":";n
      LET count=count+1
   END IF
NEXT n
PRINT

PRINT "k=2"
LET count=3
LET f=2*3*6
FOR n=3 TO 5^2-1
   LET z=n/f
   !PRINT n;":";z
   IF n=NUMER(z) THEN
      PRINT count;":";n
      LET count=count+1
   END IF
NEXT n
PRINT

PRINT "k=3"
LET count=4
LET f=2*3*5*6*10*15*30
FOR n=5 TO 7^2-1
   LET z=n/f
   !PRINT n;":";z
   IF n=NUMER(z) THEN
      PRINT count;":";n
      LET count=count+1
   END IF
NEXT n

PRINT
PRINT "k=4"
LET count=5
LET f=2*3*5*6*7*10*14*15*21*30*35*42*70*105*210
FOR n=7 TO 11^2-1
   LET z=n/f
   !PRINT n;":";z
   IF n=NUMER(z) THEN
      PRINT count;":";n
      LET count=count+1
   END IF
NEXT n

PRINT
PRINT "k=5"
LET count=6
LET f=2*3*5*6*7*10*11*14*15*21*22*30*33*35*42*55*66*70*77*105*110*154*165*210*231*330*385*462*770*1155*2310
FOR n=11 TO 13^2-1
   LET z=n/f
   !PRINT n;":";z
   IF n=NUMER(z) THEN
      PRINT count;":";n
      LET count=count+1
   END IF
NEXT n

END


------------------------------------

LET k=7
LET kk=1E6

PRINT "k=";k
DIM P(25)
MAT READ P
DATA 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97

DIM D(kk)
MAT D=ZER

FOR J=1 TO 2^K-1
   LET T=J
   LET S=1
   LET B=-1
   FOR I=1 TO K
      IF MOD(T,2)=1 THEN
         LET S=S*P(I)
         LET B=-B
      END IF
      LET T=INT(T/2)
      LET D(s)=s
   NEXT I
NEXT J

LET D(1)=0
LET FF=1
FOR dd=1 TO D(s)
   IF D(dd)><0 THEN LET FF=FF*dd
NEXT dd

LET count=k+1
FOR n=P(k) TO P(k+1)^2-1
   LET z=n/ff
   !PRINT n;":";z
   IF n=NUMER(z) THEN
      PRINT count;":";n
      LET count=count+1
   END IF
NEXT n

END
-----------------------------------

K=8 は無理でした。


昨年のプログラムを思い出して

!階乗でも、できる素数判定
OPTION ARITHMETIC RATIONAL     !有理数モード
LET z=1
LET m=1
LET count=0
FOR n=1 TO 1000
   LET m=n*m
   LET e=1/m
   LET r=e+b
   LET b=e
   IF NUMER(r)<>1 THEN
      LET count=count+1
      PRINT count;":";NUMER(r)
   END IF
NEXT n

END

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

  

戻る