Wie können wir den Sieve of Eratosthenes-Algorithmus für eine schnellere Primzahlgenerierung in Python optimieren?

Sieve of Eratosthenes verbessert: Optimierung der Erzeugung von Python-Primzahlen

Das Sieve of Eratosthenes ist ein effizienter Algorithmus zum Finden von Primzahlen bis zu einem vordefinierten Grenzwert . Allerdings kann eine naive Python-Implementierung bei größeren Grenzwerten übermäßig langsam sein.

Identifizieren von Engpässen

Im bereitgestellten Beispiel ergab die Profilerstellung, dass das Entfernen von Elementen aus erheblich Zeit in Anspruch nahm die Liste (Primzahlen). Dieser Vorgang ist rechenintensiv, insbesondere bei langen Listen.

Ersetzen von Listen durch Wörterbücher

Ein erster Versuch, dieses Problem zu beheben, bestand darin, die Liste durch ein Wörterbuch (Primzahlen) zu ersetzen. . Dies ermöglichte eine schnellere Elemententfernung. Allerdings litt der Algorithmus immer noch unter:

• Iteration über das Wörterbuch in einer undefinierten Reihenfolge
• Redundante Markierung von Faktoren von Nicht-Primzahlen

Implementierung des richtigen Algorithmus

Um den Algorithmus vollständig zu optimieren, wurde eine Korrektur durchgeführt notwendig:

1. Verwendung einer Liste anstelle eines Wörterbuchs für Primalitätsflags
2. Überspringen von Nicht-Primzahlfaktoren
3. Beginn der Faktormarkierung am Quadrat der Primzahl und nicht an ihrem Quadrat double

Das Optimierte Algorithmus

Der optimierte Algorithmus (primes_sieve2) verwendet eine Liste boolescher Werte für Primalitätsflags. Es initialisiert die Liste für alle Zahlen größer als 1 auf „True“. Anschließend durchläuft es die Liste und markiert Nicht-Primzahlen:

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

Durch die Optimierung dieser Schlüsselaspekte verbessert der Algorithmus seine Leistung und Suche erheblich zündet innerhalb von Sekunden bis zu 2 Millionen.

Das obige ist der detaillierte Inhalt vonWie können wir den Sieve of Eratosthenes-Algorithmus für eine schnellere Primzahlgenerierung in Python optimieren?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!