オイラーの贈物 1日目

1章 8ページまで

エラトステネスの篩

指定された自然数N以下の素数を発見する

•  1と2以外の偶数を排除する
• 次に3の倍数を消去する
• 次に5、7、11・・・と消去されずに残った数の倍数を消去していく
• √Nまで繰り返す

繰り返しが√Nまででいいのは√N以下の素数でない数はそれまでに消去されていて、そこから先は√Nより大きい数同士の積を消去することになり、そうなるとその積はNよりも大きくなってしまうので√Nまでの繰り返しで済むという理解でいいのか。