Wie können wir das Sieb von Eratosthenes für eine schnellere Primzahlgenerierung in Python optimieren?

Optimierung der Primzahlengenerierung mit Sieve of Eratosthenes in Python

Das Sieve of Eratosthenes ist ein altbewährter Algorithmus zur Identifizierung von Primzahlen bis zu einem bestimmten Grenzwert. Obwohl die Implementierung einfach ist, kann sie bei großen Limits überraschend langsam sein.

Langsame Implementierung

Die folgende Python-Implementierung des Siebes steht vor Herausforderungen hinsichtlich der Effizienz:

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)

Der Flaschenhals liegt in der ständigen Größenänderung der Primzahlenliste, wenn Zahlen entfernt werden. Das Entfernen eines Elements aus einer Python-Liste erfordert das Verschieben nachfolgender Elemente, was es zu einem rechenintensiven Vorgang macht.

Schnellere Implementierung mithilfe eines Wörterbuchs

Um dieses Problem zu beheben, wird eine wörterbuchbasierte Implementierung verwendet kann verwendet werden:

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

Dadurch wird ein Wörterbuch der Primalitätsflags verwaltet, wodurch die Notwendigkeit von Größenänderungsvorgängen verringert wird. Das Durchlaufen der Wörterbuchschlüssel in undefinierter Reihenfolge und das wiederholte Markieren von Nicht-Primfaktoren von Nicht-Primzahlen schränkt jedoch die Effizienz ein.

Korrigierter Algorithmus mit Liste

Die korrekte Implementierung folgt dem Sieve of Eratosthenes-Algorithmus genauer:

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

Dies verwaltet eine Liste von Primalitätsflags, Initialisierung aller Zahlen als Primzahlen außer 0 und 1. Es markiert Vielfache von Primzahlen als Nicht-Primzahlen, beginnend beim Quadrat der Primzahl, um den Prozess zu optimieren.

Durch die Behebung der Effizienzprobleme bei der Implementierung wurde dieser Algorithmus erheblich korrigiert Verbessert die Geschwindigkeit der Primzahlengenerierung, auch für große Grenzwerte.

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