Python で素数生成を高速化するためにエラトステネスのふるいを最適化するにはどうすればよいでしょうか?

Python のエラトステネスのふるいで素数生成を最適化する

エラトステネスのふるいは、指定された制限まで素数を識別するための古くからあるアルゴリズムです。実装は簡単ですが、制限が大きい場合は驚くほど遅くなる可能性があります。

実装が遅い

次の Python によるふるいの実装は、効率性の面で課題に直面しています。

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

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

ボトルネックは、数値が削除されるにつれて素数リストのサイズを継続的に変更することにあります。 Python リストから項目を削除するには、後続の要素を移動する必要があり、計算量の多い操作になります。

辞書を使用した高速な実装

これに対処するには、辞書ベースの実装を使用します。使用できます:

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

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

これは素数フラグの辞書を維持し、サイズ変更操作が必要になります。ただし、未定義の順序で辞書キーを反復処理し、非素数の非素因数を繰り返しマークすると、効率が制限されます。

List を使用した修正されたアルゴリズム

正しい実装エラトステネスのふるいアルゴリズムをより厳密に従います:

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

これは、次のリストを維持します。素数フラグ。0 と 1 を除くすべての数値を素数として初期化します。素数の倍数を非素数としてマークし、素数の 2 乗から開始してプロセスを最適化します。

実装における効率の問題に対処することで、これは修正されたアルゴリズムにより、制限が大きい場合でも素数生成の速度が大幅に向上します。

以上がPython で素数生成を高速化するためにエラトステネスのふるいを最適化するにはどうすればよいでしょうか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。