|
|
> No.190[元記事へ]
GAIさんへのお返事です。
x^nでべき指数をn=s*t*uと分解すれば、剰余計算の回数がs+t+uに減らせるのでnを素因数分解しました。
nが素数でなければ高速です。1000桁モードでも数秒です。
[投稿しようと掲示板を開いたら白石先生の投稿がありました。白石先生のプログラムではnが素数であるかに無関係で高速です。まあ、せっかく作ったので投稿します。]
追加編集[SECONDさんの投稿でさかのぼって確認しましたが、山中和義さんがすでに白石先生と同様の投稿をされていました。]
DECLARE EXTERNAL SUB prime_factor
PUBLIC NUMERIC prn(2000000),pf(100),f
DECLARE FUNCTION modn
LET x=9876543201
LET n=1234567890
LET a=6789012345
LET r=MOD(x,a)
CALL prime_factor(n) ! 素因数分解
LET k=r
FOR i=1 TO f
LET k=modn(k,pf(i),a)
NEXT i
PRINT k
!
FUNCTION modn(r,n,a) ! mod(r^n,a)
LET kk=r
FOR ii=2 TO n
LET kk=MOD(kk*r,a)
NEXT ii
LET modn=kk
END FUNCTION
END
REM ** 素因数分解 **
EXTERNAL SUB prime_factor(n)
DECLARE EXTERNAL SUB prime
LET f=0 ! 素因数の個数
LET q=n ! qは、商
LET m=1 ! 検証用変数
FOR i=1 TO 10
READ prn(i)
NEXT i
DATA 2,3,5,7,11,13,17,19,23,29
LET i=1
DO WHILE MOD(q,prn(i))=0 ! 因数判定ルーチン
LET f=f+1
LET pf(f)=prn(i) ! pf(f)はnのf番目の素因数
LET q=q/prn(i)
LET m=m*prn(i)
LOOP
LET i=2
DO WHILE prn(i)<=SQR(q)
DO WHILE MOD(q,prn(i))=0 ! 因数判定ルーチン
LET f=f+1
LET pf(f)=prn(i) ! pf(f)はnのf番目の素因数
LET q=q/prn(i)
LET m=m*prn(i)
LOOP
IF q=1 THEN EXIT DO
LET i=i+1
IF i>10 THEN CALL prime(i) ! i番目の素数
LOOP
IF q<>1 THEN
LET f=f+1
LET pf(f)=q
LET m=m*q
END IF
IF m<>n THEN PRINT "error !!"
END SUB
!
REM ** 素数列生成(k番目の素数) **
EXTERNAL SUB prime(k)
LET m30=MOD(prn(k-1),30)
IF m30=1 OR m30=23 THEN LET a=prn(k-1)+6 ELSE LET a=prn(k-1)-2*MOD(m30,3)+6
DO
LET sqra=SQR(a)
FOR j=4 TO k-1
IF MOD(a,prn(j))=0 THEN EXIT FOR
IF prn(j)>=sqra THEN
LET prn(k)=a
EXIT SUB
END IF
NEXT j
LET m30=MOD(a,30)
IF m30=1 OR m30=23 THEN LET a=a+6 ELSE LET a=a-2*MOD(m30,3)+6
LOOP
END SUB
|
|
投稿日：2008年12月24日(水)12時02分1秒