Pythonでエラトステネスの篩を実装してみる

概要

Python3でエラトステネスの篩を実装してみたいと思います。

エラトステネスの篩とは？

エラトステネスの篩 (エラトステネスのふるい、英: Sieve of Eratosthenes) は、指定された整数以下の全ての素数を発見するための単純なアルゴリズムである。古代ギリシアの科学者、エラトステネスが考案したとされるため、この名がある。

Wikipediaから抜粋
つまり素数を探索するアルゴリズムです。

実装してみた

動かしてみるとこんなかんじ

標準入力で数値を渡してあげるとその数値以下の素数をすべて返してくれます。

$ ./eratosthenes.py 
120
[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, 101, 103, 107, 109, 113]

おわりに

20桁くらいで動かしてみたらMacbookがかたまった。

入門 Python 3