【プログラミング問題】エラトステネスの篩

解答例 の対応言語

Python

 

問題

エラトステネスのふるいを使って10000以下の素数を表示してください。

 

なお、エラトステネスの篩のアルゴリズムは次の通りです。

エラトステネスの篩 - Wikipediaから抜粋、一部修正。)

  1. 探索リストに2から指定した値xまでの整数を昇順で入れる。
  2. 探索リストの先頭の数を素数リストに移動し、その倍数を探索リストから削除する。
  3. 上記2の操作を探索リストの先頭値がxの平方根に達するまで行う。
  4. 探索リストに残った数を素数リストに移動する。

 

期待する出力結果

2
3
5
7
11
13

・(中略)

9949
9967
9973

 

 

解答例