|
|
素数の末尾2桁をｃｏｕｎｔ
!Sieve of Sundaram
DECLARE EXTERNAL FUNCTION cut
OPTION ARITHMETIC NATIVE !2進モード
LET k6=9592 !5761455
DIM Ba(k6)
DIM Pa(100)
LET t0=TIME
LET k9=1E5/2 !1E8/2
DIM A(k9)
FOR i=1 TO SQR(k9)
FOR j=i TO INT(k9/3)
LET S=i+j+2*i*j
IF s>k9 THEN GOTO 10
LET A(S)=1
NEXT j
10 NEXT i
LET Ba(1)=2
LET C=1
FOR n=1 TO k9
IF A(n)=0 THEN
LET C=C+1
LET Ba(c)=n*2+1
END IF
NEXT n
FOR n=26 TO k6
LET m4=Ba(n)
LET p4=cut(m4)
LET PA(p4)=PA(p4)+1
NEXT n
FOR n=1 TO 100
IF PA(n)<>0 THEN
PRINT n;TAB(5);PA(n);TAB(11);PA(n)-239
LET z=z+PA(n)
END IF
NEXT n
PRINT z+25
LET TM=TIME-t0
PRINT USING"####." & REPEAT$("#",2):TM;
PRINT "秒"
END
EXTERNAL FUNCTION cut(m)
OPTION ARITHMETIC NATIVE
LET a$=""&STR$(m)
LET L= VAL(RIGHT$(a$,2))
LET cut=L
END FUNCTION
----------------------------------
確認用プログラム 素数リストを読み込んで計算
OPTION ARITHMETIC NATIVE
LET t0=TIME
LET k9=9592 !78498!,9592,1229, !99999989(5761455th prime)!9999991(664579th prime)
DIM A(k9)
DIM PA(100)
OPEN #1:NAME "E:\prime_1E8xv.txt",ACCESS INPUT
FOR i=1 TO k9
INPUT #1: A(i)
NEXT i
CLOSE #1
SUB count(k9)
FOR i=26 TO k9
LET pn=A(i)
LET m=10^2
DO
LET pn=pn-m
! PRINT i;":";A(i);":";pn
LOOP UNTIL pn<100
LET PA(pn)=PA(pn)+1
NEXT i
END SUB
CALL count(k9)
FOR n=1 TO 100
IF PA(n)<>0 THEN
PRINT n;TAB(5);PA(n);TAB(11);PA(n)-239
LET z=z+PA(n)
END IF
NEXT n
PRINT
PRINT z+25
LET TM=TIME-t0
PRINT USING"####." & REPEAT$("#",2):TM;
PRINT "秒"
END
--------------------------------
最初は、こんな風に、ゆっくり計算してました。
BASIC Accelerator Version 0.9.8.0
----------------------------------------
1億まで
----------------------------------------
!Sieve of Sundaram
DECLARE EXTERNAL FUNCTION cut
OPTION ARITHMETIC NATIVE !2進モード
LET k6=5761455
DIM Ba(k6)
DIM Pa(100)
LET t0=TIME
LET k9=1E8/2
DIM A(k9)
FOR i=1 TO SQR(k9)
FOR j=i TO INT(k9/3)
LET S=i+j+2*i*j
IF s>k9 THEN GOTO 10
LET A(S)=1
NEXT j
10 NEXT i
LET Ba(1)=2
LET C=1
FOR n=1 TO k9
IF A(n)=0 THEN
LET C=C+1
LET Ba(c)=n*2+1
END IF
NEXT n
FOR n=5 TO k6
LET m4=Ba(n)
LET p4=cut(m4)
LET PA(p4)=PA(p4)+1
NEXT n
FOR n=1 TO 100
IF PA(n)<>0 THEN
PRINT n;TAB(5);PA(n);TAB(14);PA(n)-144036
LET z=z+PA(n)
END IF
NEXT n
PRINT z+4
LET TM=TIME-t0
PRINT USING"####." & REPEAT$("#",2):TM;
PRINT "秒"
END
EXTERNAL FUNCTION cut(m)
OPTION ARITHMETIC NATIVE
LET a$=""&STR$(m)
LET L= VAL(RIGHT$(a$,2))
LET cut=L
END FUNCTION
結果的に ばらつきが見られます。
http://blogs.yahoo.co.jp/donald_stinger
|
|