Prime Comparison

このリポジトリでは、 エラトステネスの篩(ふるい) を使用する方法と使用しない方法の 2 つの異なるアプローチで、素数を検索するコードを比較します。

使用方法

エラトステネスの篩を使用する場合

$ python sieve/sieve.py

エラトステネスの篩を使用しない場合

$ python no_sieve/no_sieve.py

エラトステネスの篩について

エラトステネスの篩は、古代ギリシャの数学者エラトステネスによって考案された、素数を効率的に見つけるアルゴリズムです。所定の上限までの連続した数のリストを作成し、2 から始めてその倍数をリストから除外していくことで、素数だけが残るようにします。

計算量の比較

エラトステネスの篩

• 時間計算量: $\ O(n \log \log n) $

通常の素数判定方法

• 時間計算量: $\ O(n \sqrt{n}) $