【１】エラトステネスのふるい

エラトステネスは素数を組織的に拾い出すふるいを考えた数学者として知られている．まず２の倍数をすべてはじく（これで偶数はすべて消える）．次に３の倍数をすべてはじく．（４の倍数はすでに消えているから）５の倍数，７の倍数，・・・をはじく．その手順は（ｐ以外の）素数ｐの倍数を順次ふるい落とすというものである．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

［１］１から１００までの数字を順番に書く．

　　０１　０２　０３　０４　０５　０６　０７　０８　０９　１０

　　１１　１２　１３　１４　１５　１６　１７　１８　１９　２０

　　２１　２２　２３　２４　２５　２６　２７　２８　２９　３０

　　３１　３２　３３　３４　３５　３６　３７　３８　３９　４０

　　４１　４２　４３　４４　４５　４６　４７　４８　４９　５０

　　５１　５２　５３　５４　５５　５６　５７　５８　５９　６０

　　６１　６２　６３　６４　６５　６６　６７　６８　６９　７０

　　７１　７２　７３　７４　７５　７６　７７　７８　７９　８０

　　８１　８２　８３　８４　８５　８６　８７　８８　８９　９０

　　９１　９２　９３　９４　９５　９６　９７　９８　９９　100

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

［２］１を消す．最初の素数２を残し，その後出てくる２で割り切れるすべての数を消す（これで偶数はすべて消える）．

　　　　　０２　０３　　　　０５　　　　０７　　　　０９　

　　１１　　　　１３　　　　１５　　　　１７　　　　１９　

　　２１　　　　２３　　　　２５　　　　２７　　　　２９　

　　３１　　　　３３　　　　３５　　　　３７　　　　３９　

　　４１　　　　４３　　　　４５　　　　４７　　　　４９　

　　５１　　　　５３　　　　５５　　　　５７　　　　５９　

　　６１　　　　６３　　　　６５　　　　６７　　　　６９　

　　７１　　　　７３　　　　７５　　　　７７　　　　７９　

　　８１　　　　８３　　　　８５　　　　８７　　　　８９　

　　９１　　　　９３　　　　９５　　　　９７　　　　９９　

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

［３］消されない最初の数は３．３を残し，その後出てくる３で割り切れるすべての数を消す．

　　　　　０２　０３　　　　０５　　　　０７　　　　　　　

　　１１　　　　１３　　　　　　　　　　１７　　　　１９　

　　　　　　　　２３　　　　２５　　　　　　　　　　２９　

　　３１　　　　　　　　　　３５　　　　３７　　　　　　　

　　４１　　　　４３　　　　　　　　　　４７　　　　４９　

　　　　　　　　５３　　　　５５　　　　　　　　　　５９　

　　６１　　　　　　　　　　６５　　　　６７　　　　　　　

　　７１　　　　７３　　　　　　　　　　７７　　　　７９　

　　　　　　　　８３　　　　８５　　　　　　　　　　８９　

　　９１　　　　　　　　　　９５　　　　９７　　　　　　　

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

［４］４の倍数はすでに消えているから，消されない最初の数は５．５を残し，その後出てくる５で割り切れるすべての数を消す．

　　　　　０２　０３　　　　０５　　　　０７　　　　　　　

　　１１　　　　１３　　　　　　　　　　１７　　　　１９　

　　　　　　　　２３　　　　　　　　　　　　　　　　２９　

　　３１　　　　　　　　　　　　　　　　３７　　　　　　　

　　４１　　　　４３　　　　　　　　　　４７　　　　４９　

　　　　　　　　５３　　　　　　　　　　　　　　　　５９　

　　６１　　　　　　　　　　　　　　　　６７　　　　　　　

　　７１　　　　７３　　　　　　　　　　７７　　　　７９　

　　　　　　　　８３　　　　　　　　　　　　　　　　８９　

　　９１　　　　　　　　　　　　　　　　９７　　　　　　　

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

［５］６の倍数はすでに消えているから，消されない最初の数は７．７を残し，その後出てくる７で割り切れるすべての数を消す．

　　　　　０２　０３　　　　０５　　　　０７　　　　　　　

　　１１　　　　１３　　　　　　　　　　１７　　　　１９　

　　　　　　　　２３　　　　　　　　　　　　　　　　２９　

　　３１　　　　　　　　　　　　　　　　３７　　　　　　　

　　４１　　　　４３　　　　　　　　　　４７　　　　　　　

　　　　　　　　５３　　　　　　　　　　　　　　　　５９　

　　６１　　　　　　　　　　　　　　　　６７　　　　　　　

　　７１　　　　７３　　　　　　　　　　　　　　　　７９　

　　　　　　　　８３　　　　　　　　　　　　　　　　８９　

　　　　　　　　　　　　　　　　　　　　９７　　　　　　　

８，９，１０の倍数はすでに消えていて，ふるい落とされるものがない．√１００≦１０より，１００以下の数に対してこのアルゴリズムを適用すると，素数が２５個でたところでこの作業は終わる．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

さらに続けていき

［６］消されない最初の数はｐ．ｐを残し，その後出てくるｐで割り切れるすべての数を消す．このときｎより小さいすべての素数が得られるのは

　　ｐ＝［√ｎ］より小さい最大の素数

である．もし２から１０００までのすべての数字を書き出すところから始めた場合，１０００以下の素数をすべて求められたことになるのには，

　　√１０００＝３１．６

すなわち，２の倍数，３の倍数，５の倍数，・・・をふるい落としていって，３１を残しその他の３１の倍数を消せばすべての作業が終了したことになる．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝