|
|
素数の出方はランダムではなかった。1億個調べて浮かんだ奇妙な数
閲覧して興味を持ちました。素数の末尾をｃｏｕｎｔ
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(9)
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=1 TO k6
LET m4=Ba(n)
LET p4=cut(m4)
LET PA(p4)=PA(p4)+1
NEXT n
FOR n=1 TO 9
IF PA(n)<>0 THEN
PRINT n;":";PA(n)
LET z=z+PA(n)
END IF
NEXT n
PRINT z
LET TM=TIME-t0
PRINT USING"####." & REPEAT$("#",2):TM;
PRINT "秒"
END
EXTERNAL FUNCTION cut(m)
OPTION ARITHMETIC NATIVE
LET a$=""&STR$(m)
LET L=LEN(a$)
LET L1= VAL(MID$(a$,L,L))
LET cut=L1
END FUNCTION
----------------------------------------
計算結果
1 : 1440298
2 : 1
3 : 1440474
5 : 1
7 : 1440495
9 : 1440186
5761455
13.65秒
----------------------------------------
1億から2億まで
----------------------------------------
!#3978
!Re: Sieve of Sundaram サンダラムの篩(ふるい) 投稿者：nagram 様
!Sieve of Sundaram PBA
DECLARE EXTERNAL FUNCTION cut
OPTION ARITHMETIC NATIVE !2進モード
LET k6=5317482 !5761455
DIM Ba(k6)
DIM Pa(9)
LET t0=TIME
LET M=1E8/2 !素数 最小値
LET W=M-1
LET N=2E8/2 !素数 最大値
LET C=5761455 !1E8,(5761455th prime)
DIM A(1 TO N-W)
MAT A=ZER
LET S=3
LET D=4
LET k=INT(SQR(N))*3
DO
LET B=D+S*INT((M-D)/S) !ここが改良のポイント
DO UNTIL B>=M
LET B=B+S
LOOP
FOR I=B TO N STEP S
LET A(I-W)=1
NEXT I
LET S=S+2
LET D=D+3
LOOP UNTIL D>k
FOR n=1 TO N-W
IF A(n)=0 THEN
LET n1=n+W
LET C=C+1
LET CC=CC+1
LET Sundaram=n1*2+1
!PRINT c;":";Sundaram
LET Ba(cc)=Sundaram
END IF
NEXT n
FOR n=1 TO k6
LET m4=Ba(n)
LET p4=cut(m4)
LET PA(p4)=PA(p4)+1
NEXT n
FOR n=1 TO 9
IF PA(n)<>0 THEN
PRINT n;":";PA(n)
LET z=z+PA(n)
END IF
NEXT n
PRINT z
LET TM=TIME-t0
PRINT USING"####." & REPEAT$("#",2):TM;
PRINT "秒"
END
EXTERNAL FUNCTION cut(m)
OPTION ARITHMETIC NATIVE
LET a$=""&STR$(m)
LET L=LEN(a$)
LET L1= VAL(MID$(a$,L,L))
LET cut=L1
END FUNCTION
----------------------------------------
計算結果
1 : 1329469
3 : 1329374
7 : 1329577
9 : 1329062
5317482
13.74秒
まだ、まだです。最初は、沢山時間がかかりました。
----------------------------------------
乱数 計算の度に数値が変化します。
----------------------------------------
DIM A(4)
RANDOMIZE
FOR t=1 TO 5761455-2
LET n=1+IP(4*RND)
LET A(n)=A(n)+1
! PRINT n
NEXT t
PRINT a(1)
PRINT a(2)
PRINT a(3)
PRINT a(4)
END
（素数の末尾はかならず1、3、7、9なので、確率は4つにひとつ）。
http://blogs.yahoo.co.jp/donald_stinger
|
|