定義

エラトステネスの篩は、古代ギリシャの数学者エラトステネスが発明した素数発見アルゴリズムです。ふるいで砂をこすように、倍数を一つずつ消していくと素数だけが残ります。

主な特性

• ✓2から始めて、まだ消されていない数字が次の素数
• ✓各素数の倍数をすべて消していく
• ✓√Nまでの検査で十分（最適化）
• ✓O(n log log n)の時間計算量で非常に高速

時間計算量