素数列挙2

さて、前回よりましな処理にしましょう。
素数は3以降「6n±1」の範囲にしか存在しないことを利用します。
・・・と言ってもそもそも「6n±1」が範囲にあるの？って話ですね。

簡単に説明すると
6n±4　は　常に2の倍数
6n±3　は　常に3の倍数

6n±2　は　常に2の倍数

6n±1　は　常に奇数で3以降の全ての素数を「含み」ます。

こんな感じです。２と３の倍数を全て除外してステップするので２と３は事前に素数として登録します。

(まぁ、考え方的には素数は「6n+1」と「6n+5」なんですが、5は詰まり6より一つ小さい数なので「6n+5」→「6n-1」となり結果「6n±1」に集約されます)

処理内容は：

'#2と3は事前登録。

'#素数は常に「6n±1」の為、開始値6で6ずつ加算ループ(2と3の倍数永久除外)

'#　「-1と+1の割り切れないフラグ」をtrue

'#　登録済素数で割り算ループ

'#　　値-1割れたら「-1割り切れないフラグ」false

'#　　値+1割れたら「+1割り切れないフラグ」false

'#　　「-1と+1の割り切れないフラグ」がfalseなら抜ける

'#　　最終値でかつ「-1割り切れないフラグ」trueなら素数登録

'#　　最終値でかつ「+1割り切れないフラグ」trueなら素数登録

dim n:redim n(1):n(0)=2:n(1)=3

for i=6 to 10000 step 6
    mf=1:pf=1
    for j=0 to ubound(n)
        if mf then mf=(i-1) mod n(j)
        if pf then pf=(i+1) mod n(j)
        if mf+pf=0 then exit for
        if j=ubound(n) then
            if mf then redim Preserve n(ubound(n)+1):n(ubound(n))=i-1
            if pf then redim Preserve n(ubound(n)+1):n(ubound(n))=i+1
        end if
    next
next
wsh.echo join(n)