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

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

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

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

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

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

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

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

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

【２】１０を法とするエラトステネスのふるい

　　　　　０２　０３　　　　０５　　　　０７　　　　　　　

　　１１　　　　１３　　　　　　　　　　１７　　　　１９　

　　　　　　　　２３　　　　　　　　　　　　　　　　２９　

　　３１　　　　　　　　　　　　　　　　３７　　　　　　　

　　４１　　　　４３　　　　　　　　　　４７　　　　　　　

　　　　　　　　５３　　　　　　　　　　　　　　　　５９　

　　６１　　　　　　　　　　　　　　　　６７　　　　　　　

　　７１　　　　７３　　　　　　　　　　　　　　　　７９　

　　　　　　　　８３　　　　　　　　　　　　　　　　８９　

　　　　　　　　　　　　　　　　　　　　９７　　　　　　　

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