|
|
!210n+k篩
OPTION ARITHMETIC NATIVE
LET t0=TIME
LET k=316241 !MAX 100,008,370,081
LET k2=27294
DIM P(k)
DIM A(k2) !素数
SUB prime(v) !エラトステネスの奇数列篩
LET k9=v
LET h1=1
LET A(h1)=2
LET h1=2
FOR n1=3 TO k9 STEP 2
IF P(n1)=0 THEN
LET A(h1)=n1
LET h1=h1+1
IF h1>k9+1 THEN GOTO 20
END IF
FOR k1=n1 TO k9 STEP 2
LET m1=n1*k1
IF m1>k9 THEN GOTO 10
LET P(m1)=1
NEXT k1
10 NEXT n1
20
END SUB
CALL prime(k)
DIM B(48)
DATA 1,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109
DATA 113,121,127,131,137,139,143,149,151,157,163,167,169,173,179,181,187,191,193,197,199,209
MAT READ B
LET Q=210 !1E8=5761455(0.28秒)
LET k1=1E8 !1E9=50847534(3.96秒) 1E6=78498
LET ka=IP(k1/Q ) !1E10=455052511(54.25秒)
LET kb=k1 !1E11=4118054813(686.84秒)11分26秒84 (686.93秒)
LET kc=IP(SQR(k1)) !1E+8=1229, 1E+7=447
LET kd=IP(ka/11+11)
DIM D(ka)
LET k3=0
FOR n=1 TO k2
LET PP=A(n)
IF PP > kc THEN EXIT FOR
LET k3=k3+1
NEXT n
!PRINT "k3=";k3;kc
LET cj =46
FOR r=1 TO 48
LET rr=B(r)
MAT D = ZER
FOR t=5 TO k3
LET x=A(t) !素数篩
IF x^2 > k1 THEN EXIT FOR
IF MOD(x-rr,Q)=0 THEN
LET y=(x-rr)/Q
FOR f=1 TO kd
LET ii=x*f+y
IF ii>ka THEN EXIT FOR
LET D(ii)=1
NEXT f
ELSE
FOR i=1 TO 48
LET rv=B(i)
IF MOD(x*rv+rr,Q)=0 THEN
LET y=-(x*rv+rr)/Q
EXIT FOR
END IF
NEXT i
FOR f=1 TO kd
LET ii=x*f+y
IF ii > ka THEN EXIT FOR
IF ii <= 0 THEN GOTO 100
LET D(ii)=1
100 NEXT f
END IF
!PRINT x;kd;f;ii;ka
NEXT t
FOR n=1 TO ka
IF n*Q+rr>k1 THEN EXIT FOR
IF D(n)=0 THEN LET cj=cj+1
NEXT n
NEXT r
PRINT cj
LET TM=TIME-t0
PRINT USING"####." & REPEAT$("#",2):TM;
PRINT "秒"
END
動作報告です。
Paract BASIC プログラム 210n+k篩 素数の個数を数えるプログラム
動作環境
Intel Core i7 -8565U mouse m-Book MB-R500 ノート PC
Windows Version
Microsoft Windows 10 (10.0) Professional 64-bit
Paract BASIC Ver. 2.1.2.4 Rev.2 (2021.06.19)
Lazarus fpc-3.2.2-win64
lazarus-2.2.0RC1-fpc-3.2.2-win64.exe 2021-07-08 199.7 MB
lazarus-2.2.0RC1-fpc-3.2.2-cross-i386-win32-win64.exe 2021-07-08 55.1 MB
|
|