【Python】高速かつ簡単にNまでの素数を求めるプログラム【エラトステネスの篩】
Pythonの練習課題として，Nまでの素数を求めるプログラムを「エラトステネスの篩」というアルゴリズムを用いて実装しました．
エラトステネスの篩（ふるい）とは
今回は，wikipediaの解説を元にプログラムを実装しました．
エラトステネスの篩 - Wikipedia
アルゴリズム
指定された整数x以下の全ての素数を発見するアルゴリズム。右のアニメーションでは以下のステップにそって2 から 120 までの数に含まれる素数をさがしている。
ステップ 1
探索リストに2からxまでの整数を昇順で入れる。
ステップ 2
探索リストの先頭の数を素数リストに移動し、その倍数を探索リストから篩い落とす。
ステップ 3
上記の篩い落とし操作を探索リストの先頭値がxの平方根に達するまで行う。
ステップ 4
探索リストに残った数を素数リストに移動して処理終了。
非常にシンプルなアルゴリズムで，個人的には速さよりも実装の簡単さの方が今回はありがたかったです．
エラトステネスの篩の速さについてはこちらのサイトがわかりやすく参考になりそうです．
プログラム
実際にPythonで実装したコードがこちらです．
実行結果
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
正直正しく実装できているかは不安ですが，100までの素数は正しく得られました．
