本当は遅い「似非エラトステネスの篩」の罠

この記事は？ インターネット上でエラトステネスの篩の実装を検索すると、かなりの割合で、エラトステネスの篩とよんでいいのか怪しい「似非エラトステネスの篩」とでも称すべきものがみられます。 この記事では、「試し割り」「似非エラトステネスの篩」「エラトステネスの篩」の3つのアルゴリズムを比較して、その違いを解説します。 3つのアルゴリズムの比較 1. 試し割り 実装 まず他のアルゴリズムに対する評価基準として、試し割りのアルゴリズムを示します。 試し割りは、nが素数であるかを判定するために\sqrt{n}以下の全ての素数で割って確認するアルゴリズムです。 import sys # limit 以下の全ての素数を返す def list_primes(limit): primes = [] for i in range(2, limit + 1): is_prime = True for p in

[t_f_m]

アイデア（＝アルゴリズム）は同じと本文中でも明言されてるけど、ここでの真と似非をわけてるの、AtCoder等の、プログラミングコンテストでも使えるかどうかの真・似非なのは注意

[yarumato]

“ネット上では怪しい「似非エラトステネスの篩」とでも称すべきもの（試し割りの倍の時間がかかる）がみられます。3つのアルゴリズムを比較して、違いを解説。正しい実装は試し割りに対して10倍以上高速”

[mozukuyummy]

isPrime を32ずつ区切ったbit列の配列にすればもっと速くなりそうだけど？

[odakaho]

配列サイズの変更周りが重いということね。

[Rion778]

剰余使って判定するの、アイデアとしても正しくない気がするけど自信がない