エラストテレスの篩(ふるい)

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…\)なので、終了です。残っている数字が素数になります。

おすすめ