|
|
> No.3566[元記事へ]
CurPrimeを広域変数にすると主プログラム内でCurPrimeの値を変更することが可能となり、CurePrime^2より小さく変更すれば、次にNextPrimeを実行したときには変更したCurPrimeの次の素数が得られます。
この性質を利用して、引数より大きな最小の素数を返す関数を作成しました。UBASICの関数nxtprm(n)と同じ機能です。
また、2と3の倍数をあらかじめ除き、配列sの大きさを3分の1に圧縮しました。
REM 関数 NextPrime(n) … nより大きい最小の素数。nは整数でなくともよい。
DECLARE EXTERNAL FUNCTION Primes.NextPrime
LET p=1
FOR i=1 TO 30
LET p=NextPrime(p)
PRINT p
NEXT i
RANDOMIZE
FOR i=1 TO 30
LET a=INT(100000*RND)
LET p=NextPrime(a)
PRINT a;p
NEXT i
PRINT NextPrime(99990) ! maxn=100000のときの最大素数は99991。これより大きい引数はエラー。
END
!
MODULE Primes
PUBLIC FUNCTION NextPrime
SHARE NUMERIC s(33333),maxn,MaxPrime ! 配列sのサイズは変更可能だが、必ず定数で指定。
LET maxn=3*SIZE(s)+1 ! maxnまでの素数に対応
MAT s=ZER
WHEN EXCEPTION IN
FOR i=8 TO maxn STEP 10 ! 5の倍数
LET s(i)=1
LET s(i+3)=1
NEXT i
USE
END WHEN
LET MaxPrime=5
! j=5,7,11,13,17,19,23,25,29,31,35,37,41,43,47,49,53,55,59,61,65,67,71,73,77,79
! INT(j/3)=1,2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26
!s(INT(j/3))=0,0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0
EXTERNAL FUNCTION NextPrime(n)
IF n<5 THEN
LET NextPrime=5
IF n<3 THEN LET NextPrime=3
IF n<2 THEN LET NextPrime=2
EXIT FUNCTION
END IF
LET n=INT(n)
LET k=MOD(n,6)
IF k<>1 AND k<>5 THEN LET n=n-ABS(k-1)
IF n<=MaxPrime^2 THEN CALL PrimeCheck(n)
!
IF MOD(MaxPrime,6)=1 THEN LET add=4 ELSE LET add=2
WHEN EXCEPTION IN
DO ! エラトステネスの篩
LET ex=1
DO
LET MaxPrime=MaxPrime+add
LET add=6-add
LOOP UNTIL s(INT(MaxPrime/3))=0
LET ex=0
FOR j=MaxPrime^2 TO maxn STEP 6*MaxPrime
LET s(INT(j/3))=1
IF MOD(j+2*MaxPrime,3)>0 THEN LET s(INT((j+2*MaxPrime)/3))=1 ELSE LET s(INT((j+4*MaxPrime)/3))=1
NEXT j
LOOP UNTIL MaxPrime>=INT(SQR(n))
USE
IF ex=1 THEN EXIT FUNCTION ! エラー NextPrime=0
END WHEN
CALL PrimeCheck(n)
SUB PrimeCheck(p) ! pより大きい素数の検索
IF MOD(p,6)=1 THEN LET add=4 ELSE LET add=2
WHEN EXCEPTION IN
DO
LET p=p+add
LET add=6-add
LOOP UNTIL s(INT(p/3))=0
LET NextPrime=p
USE ! エラー NextPrime=0
END WHEN
EXIT FUNCTION
END SUB
END FUNCTION
END MODULE
|
|