エラトステネスのふるい

「エラトステネスのふるい」は，指定した自然数 $N$ 以下の素数を求めるアルゴリズムの一つです．このアルゴリズムは次の(1)～(5)の手順で構成されています．

(1) 自然数が一列に1から左から順に $N$ まで並んで書かれた表，碁石，マーカーを用意します．

(2) 碁石をまず1の数字の上に置きます．

(3) 碁石を一つ右隣の数字の上に置きます．ただし，碁石が $\sqrt N$ より大きい数字の上に置かれた場合，(5)の手順に移ります．

(4) 置いた数字にマーカーで印が付けられていない場合，その数字以外のその数字の倍数にマーカーで印をつけた後，(3)の手順に戻ります．置いた数字にマーカーで印が付けられている場合，何もせずに(3)の手順に戻ります．

(5) 表に書かれた自然数の中で，印がついていないものが素数となります．

(3)について補足しておきます．

$N$ が素数かどうかを判断するには， $\sqrt N$ 以下の自然数で割り切れるかどうかを調べれば十分です．なぜなら，もし $N$ が $\sqrt N$ より大きな自然数を因数に持つならば， $N$ は $\sqrt N$ より小さな自然数を因数に持つはずであり，そのような自然数が存在するかどうかはすでに調べられているからです．

同様に， $M\ ＜\ N$ なる自然数 $M$ についても，素数かどうかの判定は $\sqrt M$ 以下の自然数で割り切れるかどうかを調べれば十分です．そして， $\sqrt M\ ＜\ \sqrt N$ であるから，結局 $\sqrt N$ 以下の自然数で割り切れるかどうかを調べれば，表に書かれたすべての自然数について素数かどうかの判定が行われたことになります．そのため，(3)から(5)に移る条件は「碁石が $\sqrt N$ より大きい数字の上に置かれた場合」，になるのです．