[解決済み】エラトステネスのふるい - 素数を求める Python

質問

はっきり言って、これは宿題の問題ではありません :)

今作っている数学のアプリケーションのために素数を探したいと思っていたら、次のようなものに出会いました。 エラトステネスの篩（ふるい のアプローチになります。

私はPythonでその実装を書きました。しかし、恐ろしく遅いのです。例えば、200万以下のすべての素数を見つけたい場合。20分もかかってしまいます。(この時点で止めました)。どうすれば速くなるのでしょうか？

def primes_sieve(limit):
    limitn = limit+1
    primes = range(2, limitn)

    for i in primes:
        factors = range(i, limitn, i)
        for f in factors[1:]:
            if f in primes:
                primes.remove(f)
    return primes

print primes_sieve(2000)

UPDATEです。 このコードのプロファイリングをしてみたところ、リストから要素を削除するのに非常に多くの時間が費やされていることがわかりました。最悪の場合）リスト全体を走査して要素を見つけ、それを削除してリストを再調整しなければならないことを考えると、非常に理解しやすい。とにかく、私はリストを捨てて、辞書を作った。私の新しい実装は

def primes_sieve1(limit):
    limitn = limit+1
    primes = dict()
    for i in range(2, limitn): primes[i] = True

    for i in primes:
        factors = range(i,limitn, i)
        for f in factors[1:]:
            primes[f] = False
    return [i for i in primes if primes[i]==True]

print primes_sieve1(2000000)

解決方法は？

正しいアルゴリズムを実装しているとは言い難い。

最初の例では primes_sieve は、(アルゴリズムのように)プライマリフラグを打ったり外したりするリストを保持せず、代わりに整数のリストを連続的にリサイズします。これは非常に高価です。

2つ目の例では primes_sieve1 を維持します。 ディクショナリー これは正しい方向への一歩ですが、辞書を不定な順序で繰り返し、(アルゴリズムのように素数の素数だけでなく)素数の素数を冗長に取り出しています。この問題は、キーをソートして素数以外をスキップすることで解決できますが(これですでに1桁速くなります)、それでもリストを直接使用する方がはるかに効率的です。

正しいアルゴリズム（辞書の代わりにリストを使用）は、次のようになります。

def primes_sieve2(limit):
    a = [True] * limit                          # Initialize the primality list
    a[0] = a[1] = False

    for (i, isprime) in enumerate(a):
        if isprime:
            yield i
            for n in range(i*i, limit, i):     # Mark factors non-prime
                a[n] = False

(なお、これには、プライムのマス目からプライム以外のマーキングを開始するというアルゴリズムの最適化も含まれています( i*i ) の2倍ではなく、3倍です)。