エラストテレスの篩(ふるい)
1.エラストテレスの篩
エラストテレスの篩とは
指定された整数以下の全ての素数を発見するための手順です。
手順
1.2からnまでの数字を並べる。
2.並べられてる数字の中で一番小さい数PをP以外の倍数を、並べた数字から消していく。
3.2の操作を繰り返していきPが\sqrt{n}を超えたら終了。
4.残った数字が素数となる。
n=50で考えていきましょう。
1.並べる
2.1.P=2で2以外の倍数を消していく。
2.2.P=3で3以外の倍数を消していく。
2.3.P=5で5以外の倍数を消していく。
2.4.P=7で7以外の倍数を消していく。
3.\sqrt{50}=7.0…なので、終了です。残っている数字が素数になります。
