Wie kann ich einen einfachen Primzahlgenerator in Python optimieren?

Optimierung eines einfachen Primzahlgenerators in Python

Der bereitgestellte Python-Code zielt darauf ab, Primzahlen zu generieren, muss jedoch aus Effizienzgründen verbessert werden.

Probleme mit dem Originalcode:

1. Die Schleife prüft auf Teilbarkeit, gibt die Anzahl jedoch falsch aus, selbst wenn ein Teiler gefunden wird.
2. Die continue-Anweisung beendet die aktuelle Iteration, sollte aber durch break ersetzt werden, um die Suche ganz zu beenden, wenn ein Teiler gefunden wird.

Verbessert Code:

import math

def main():
    count = 3
    while True:
        isprime = True
        for x in range(2, math.ceil(math.sqrt(count)) + 1):
            if count % x == 0: 
                isprime = False
                break
        if isprime:
            print(count)
        count += 1

Erklärung:

• Die äußere Schleife erhöht den Zählwert, um auf die nächste mögliche Primzahl zu testen.
• Die innere Schleife läuft nun bis zur Quadratwurzel der Zählung, da jeder Teiler, der größer als die Quadratwurzel ist, einen entsprechenden Teiler unterhalb des Quadrats hat Wurzel.
• Wenn die Anzahl durch ein beliebiges x teilbar ist, wird das isprime-Flag auf False gesetzt und die innere Schleife wird unterbrochen.
• Wenn keine Teiler gefunden werden, ist die Anzahl eine Primzahl und wird gedruckt .

Erweiterte Prime Generation:

Für eine effizientere Prime Generation ist die Empfohlen wird ein Sieb aus Eratosthenes. Hier ist eine optimierte Python-Implementierung mit Kommentaren:

def gen_primes():
    D = {}
    q = 2
    while True:
        if q not in D:
            yield q
            for later in range(q * q, 1000000, q):
                D[later] = [q]
        else:
            for later in range(q + D[q][0], 1000000, q):
                D.setdefault(later, []).append(q)
            del D[q]
        q += 1

Das obige ist der detaillierte Inhalt vonWie kann ich einen einfachen Primzahlgenerator in Python optimieren?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!