日記　2014年07月

09日

素数判定プログラムの下の方に書いた多行エラトステネスの実装、30行まで。多行化の恩恵はほとんど感じられなかった。先のページのデモより速いのは9年前のわたしが書いたコードが下手だったというだけの違いである。

ちなみに配列数の節約のためにすべての素数候補の配列を作ってから削るのではなく新たな候補に対して既存の素数で割っている。6行と30行はそれぞれ6の倍数・30の倍数ごとに判定するので、1000000を入力しても1000020まで範囲に勝手に含む点に注意。

先のページより表を持ってきている。30の倍数で区切った範囲内で、素数が含まれる列がp=1,7,11,13,17,19,23,29とした時30i+pで表せることを利用して候補を絞る。初期配列pを作るコストが難物である点が問題で、この行数はn!行に拡張するほど効率が上がる。