|
|
素数積篩
----------------------------------------
!10n+ k篩
OPTION ARITHMETIC NATIVE
LET t0=TIME
LET k=10039
LET k2=1233
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)
OPEN #1: TextWindow1
ERASE #1
FOR zx=1 TO 4
PRINT #1:STR$(A(zx))&",";
NEXT zx
DIM B(4)
DATA 1,3,7,9
MAT READ B
LET ka=1E8/10
LET kb=ka*10
LET kc=1229
DIM D(ka)
DIM W(kb)
FOR r=1 TO 4
LET rr=B(r)
MAT D = ZER
FOR t=2 TO kc
IF t=3 THEN GOTO 90
LET x=A(t)
IF MOD(x+rr,10)=0 THEN
LET y=-(x+rr)/10
GOTO 80
END IF
IF MOD(x-rr,10)=0 THEN
LET y=(x-rr)/10
GOTO 80
END IF
FOR i=-x TO 0 !!
IF MOD(10*i+rr,x)=0 THEN LET y=i
NEXT i
80
FOR f=1 TO ka
IF x*f+y>ka THEN GOTO 90
IF x*f+y=0 THEN GOTO 90
LET D(x*f+y)=1
NEXT f
90 NEXT t
FOR n=1 TO ka
IF D(n)=1 THEN GOTO 100
IF n*10+rr>kb THEN GOTO 100
LET W(n*10+rr)=1
! LET cj=cj+1
100 NEXT n
NEXT r
LET ci=4
FOR v=11 TO kb STEP 2
IF W(v)=1 THEN
LET ci=ci+1
PRINT #1:STR$(v)&",";
END IF
NEXT v
CLOSE #1
PRINT ci
LET TM=TIME-t0
PRINT USING"####." & REPEAT$("#",2):TM;
PRINT "秒"
END
--------------------------------------
素数積篩 無限の組み合わせが可能
--------------------------------------
!100n+k篩
OPTION ARITHMETIC NATIVE
LET t0=TIME
LET k=10039
LET k2=1233
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)
OPEN #1: TextWindow1
ERASE #1
FOR zx=1 TO 25
PRINT #1:STR$(A(zx))&",";
NEXT zx
DIM B(40)
DATA 1,3,7,9,11,13,17,19,21,23,27,29,31,33,37,39,41,43,47,49
DATA 51,53,57,59,61,63,67,69,71,73,77,79,81,83,87,89,91,93,97,99
MAT READ B
LET kd=100
LET ka=1E8/kd
LET kb=ka*kd
LET kc=1229 !1E+8=1229, 1E+7=447
DIM D(ka)
DIM W(kb)
FOR r=1 TO 40
LET rr=B(r)
MAT D = ZER
FOR t=2 TO kc
IF t=3 THEN GOTO 90
LET x=A(t)
IF MOD(x+rr,kd)=0 THEN
LET y=-(x+rr)/kd
GOTO 80
END IF
IF MOD(x-rr,kd)=0 THEN
LET y=(x-rr)/kd
GOTO 80
END IF
FOR i=-x TO 0 !!
IF MOD(kd*i+rr,x)=0 THEN LET y=i
NEXT i
80
FOR f=1 TO ka
IF x*f+y>ka THEN GOTO 90
IF x*f+y=0 THEN GOTO 90
LET D(x*f+y)=1
NEXT f
90 NEXT t
FOR n=1 TO ka
IF D(n)=1 THEN GOTO 100
IF n*kd+rr>kb THEN GOTO 100
LET W(n*kd+rr)=1
! LET cj=cj+1
100 NEXT n
NEXT r
LET ci=25
FOR v=101 TO kb STEP 2
IF W(v)=1 THEN
LET ci=ci+1
PRINT #1:STR$(v)&",";
END IF
NEXT v
CLOSE #1
PRINT ci
LET TM=TIME-t0
PRINT USING"####." & REPEAT$("#",2):TM;
PRINT "秒"
END
----------------------------------------
http://blogs.yahoo.co.jp/donald_stinger
|
|