本当は遅い「似非エラトステネスの篩」の罠この記事は？ インターネット上でエラトステネスの篩の実装を検索すると、かなりの割合で、エラトステネスの篩とよんでいいのか怪しい「似非エラトステネスの篩」とでも称すべきものがみられます。 この記事では、「試し割り」「似非エラトステネスの篩」「エラトステネスの篩」の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
