algorithm - エラトステネスのふるいの実装を理解するのに役立ちます

Answer 1

私は、programmingpraxis のウェブサイトでのコメントの助けを借りて、それを理解したと思います。

問題を言い換えるstartjと、リストでは(+ (* 2 i i) (* 6 i) 3)、つまりとして定義されてい2i^2 + 6i + 3ます。

私は当初、この式が とどのように関連しているか理解できませんでしpた。数値の「ふるい分け」はpから開始する必要があるため、これは に関連するものである必要があるp^2と考えました。startj4i^2 + 12i + 9

ただし、startjはベクトル へのインデックスvであり、3 から始まる奇数が含まれています。したがって、p^2実際のインデックスは です(p^2 - 3) / 2。

式の展開: (p^2 - 3) / 2= ([4i^2 + 12i + 9] - 3) / 2= 2i^2 + 6i + 3- これは の値ですstartj。

startjとして定義する方が明確だったかもしれませんが(quotient (- (* p p) 3) 2)、とにかく-それで解決すると思います:)

Answer 2

David Seiler：おそらく最も明確ではありませんが、基本的なSieveを実装することに加えて、演習で説明した3つの最適化も実装する必要があります。

ハルト：それは私の2番目の練習でした。私はまだ自分の文体を試していました。

エフェミエント：正解です。

プログラミング実践の私のコメントでより完全な説明を参照してください。

編集：ProgrammingPraxisにコメントを追加しました。そして、実際にコードを見ると、数式の6という数字の導出について間違っていました。すみません、誤解を招きます。