エラストテレスの篩(ふるい)
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…\)なので、終了です。残っている数字が素数になります。
