Wie kann man in Python effizient einen unendlichen Strom von Primzahlen generieren?

Wie implementiert man einen effizienten unendlichen Primzahlgenerator in Python?

Eine effiziente Möglichkeit, eine unendliche Reihe von Primzahlen zu erzeugen, ist die Verwendung des Siebs von Eratosthenes. Dadurch werden Nicht-Primzahlen eliminiert, indem ihre Vielfachen iterativ markiert werden. Obwohl diese Methode effektiv ist, erfordert sie viel Speicher zum Speichern der markierten Zahlen.

erat2

Hier ist die erat2-Funktion aus dem Kochbuch der Python-Standardbibliothek, die sein kann Wird verwendet, um eine unendliche Reihe von Primzahlen zu erzeugen Zahlen:

import itertools as it
def erat2( ):
    D = {  }
    yield 2
    for q in it.islice(it.count(3), 0, None, 2):
        p = D.pop(q, None)
        if p is None:
            D[q*q] = q
            yield q
        else:
            # old code here:
            # x = p + q
            # while x in D or not (x&1):
            #     x += p
            # changed into:
            x = q + 2*p
            while x in D:
                x += 2*p
            D[x] = p

erat2a

Die erat2-Funktion kann durch die Vermeidung unnötiger Prüfungen weiter optimiert werden:

import itertools as it
def erat2a( ):
    D = {  }
    yield 2
    for q in it.islice(it.count(3), 0, None, 2):
        p = D.pop(q, None)
        if p is None:
            D[q*q] = q
            yield q
        else:
            # old code here:
            # x = p + q
            # while x in D or not (x&1):
            #     x += p
            # changed into:
            x = q + 2*p
            while x in D:
                x += 2*p
            D[x] = p

erat3

Für eine noch schnellere Leistung nutzt die erat3-Funktion die Tatsache, dass alle Primzahlen (außer 2, 3 und 5) Modulo 30 ergeben nur acht spezifische Zahlen. Dadurch wird die Anzahl der während des Siebvorgangs erforderlichen Überprüfungen erheblich reduziert:

import itertools as it
def erat3( ):
    D = { 9: 3, 25: 5 }
    yield 2
    yield 3
    yield 5
    MASK= 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0,
    MODULOS= frozenset( (1, 7, 11, 13, 17, 19, 23, 29) )

    for q in it.compress(
            it.islice(it.count(7), 0, None, 2),
            it.cycle(MASK)):
        p = D.pop(q, None)
        if p is None:
            D[q*q] = q
            yield q
        else:
            x = q + 2*p
            while x in D or (x%30) not in MODULOS:
                x += 2*p
            D[x] = p

Diese Optimierungen können zu erheblichen Leistungsverbesserungen führen, insbesondere bei der Generierung großer Primzahlen.

Das obige ist der detaillierte Inhalt vonWie kann man in Python effizient einen unendlichen Strom von Primzahlen generieren?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!