【Python】エラトステネスの篩の実装方法(numpyの方が早かった)

エラトステネスの篩は、素数を検出するアルゴリズムの一つです。愚直な素数検出の方法よりも高速ですが、メモリを多く消費する性質を持っています。

ピンとくる方もいるかも知れませんが、10桁の素数の一覧を作成するために実装してみました。また、numpyを使用した方が高速に処理が実行できたため、そちらの実装も記載しておきます。

エラトステネスの篩を実装してみたいなという方は参考にしてみてください。

エラトステネスの篩とは

エラトステネスの篩（Sieve of Eratosthenes）は、古代ギリシャの科学者であるエラトステネスによって発見された素数を見つけるための古典的なアルゴリズムです。

篩（ふるい）の文字通りに、整数の一覧から素数を見つけ出しその素数の倍数を篩にかけていく手順を踏みます。具体的な手順に関してはwikiを引用します。

指定された整数x以下の全ての素数を発見するアルゴリズム。

ステップ 1

120要素の配列の1番目にfalseを、2番目以降に全てtrueを入れる。

ステップ 2

配列の先頭から順に走査し、trueの要素を見つけたらその添字pを素数リストに追加し、配列の  以上のpの倍数番目をfalseにする。

ステップ 3

上記の篩い落とし操作を、走査している要素の添字がxの平方根に達するまで行う。

ステップ 4

最後までtrueだった要素の添字を素数リストに追加して処理終了。

https://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E7%AF%A9

エラトステネスの篩の実装

ライブラリを使用しない方法

numpyを使用する方法

numpyを使用する時との速度比較

100,000、100,000,000までそれぞれの手法で3回実行し、その処理時間の平均を取ってみました。単位は秒です。

エラトステネスの篩の実装方法のまとめ

この記事では、古典的な素数判定アルゴリズムであるエラトステネスの篩の実装を行いました。

手順通りの実装ではありますが、ステップ2のふるいにかける数の対象は以降のもので良いというところはたまに見落としている人がいるので気をつけましょう。

一定大きな数に対しての素数検出であれば、実装コストと処理速度のコスパが良いかなと思うので興味のある人は実装活用してみてください。