|
|
Wikipedia「サンダラムの篩」を参照しました。
! Sieve of Sundaram サンダラムの篩(ふるい)
! 素数リスト作成プログラム
LET t0=TIME
ASK DIRECTORY d$
LET t0=TIME
LET f_name1$="PRIME_N_P100003" ! ファイル名
LET f1$=d$&"\"&f_name1$&".txt"
PRINT "ファイル保存場所[1] = ";f1$
OPEN #1: NAME f1$
ERASE #1
PRINT #1:2
PRINT #1:3
LET N=50005 !素数100003まで生成 99991(9592nd prime)
DIM A(N)
FOR I=1 TO N
LET A(I)=0
NEXT I
LET A(1)=1
LET S=3
LET D=4
LET U=INT(N/3)
100 FOR I=D TO N STEP S
LET A(I)=1
NEXT I
LET S=S+2
200 LET D=D+3
IF A(D)=0 THEN 200
IF D>(N/3) THEN 300
GOTO 100
300 FOR I=1 TO N
IF A(I)=1 THEN 400
LET z=I*2+1
PRINT #1:z
400 NEXT I
PRINT TIME-t0;"秒で計算しました"
END
実行結果
ファイル保存場所[1] = E:\10進BASIC\サンダラムの篩\PRIME_N_P100003.txt
.64 秒で計算しました(AMD 2.4GHz Win8.2 32bt の環境)
----------------------------------------------------------------
素数 2と3は出ませんので、プリント出力しています。
プログラムを保存したフォルダーに素数リスト ファイル生成されます。
素数生成の処理速度を高速化する狙いで書きました。
PRINT 出力時での比較ではエラトステネスの篩と同程度でした。
http://blogs.yahoo.co.jp/donald_stinger
|
|
