Sieve of Sundaram サンダラムの篩(ふるい)

 投稿者:たろさ  投稿日:2015年10月 2日(金)02時40分53秒
  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

 

Re: Sieve of Sundaram サンダラムの篩(ふるい)

 投稿者:たろさ  投稿日:2015年10月 5日(月)21時12分12秒
  > No.3870[元記事へ]

たろささんへのお返事です。

OPTION ARITHMETIC NATIVE

入れたら処理速度が速くなった気がします。

メモリー限界まで

素数リストの精度確認は下記程度の確認です。

97(25th prime)
997(168th prime)
9973(1229th prime)
99991(9592nd prime)
999983(78498th prime)
9999991(664579th prime)
99999989(5761455th prime)
100000007(5761456th prime)


199999991(11078937th prime)

113.71秒 1分53.71秒

2億以上は 2億1千万も試しましたが駄目でした。

1億単位でプログラムが書けると良いのですが

今の私には無理です。

http://blogs.yahoo.co.jp/donald_stinger

 

戻る