Was ist der schnellste Weg, alle Primzahlen unterhalb einer bestimmten ganzen Zahl N zu finden?

Schnellste Möglichkeit, alle Primzahlen unterhalb von N aufzulisten

Dieses Codefragment enthält eine Python-Implementierung einer Methode zum effizienten Generieren einer Liste von Primzahlen bis zu einer bestimmten Ganzzahl.

    def get_primes(n):
        numbers = set(range(2, n + 1))
        primes = []
        while numbers:
            p = numbers.pop()
            primes.append(p)
            numbers.difference_update(set(range(p * p, n + 1, p)))
        return primes

Zeit Komplexität:

Die zeitliche Komplexität des gegebenen Codes beträgt O(n log log n), da er Sieve of Eratosthenes zur Berechnung der Primzahlen verwendet.

Implementierungshinweise :

• Der Code initialisiert einen Satz Zahlen, der alle ganzen Zahlen von 2 bis enthält n.
• Es entfernt iterativ Nicht-Primzahlen aus Zahlen, indem es alle Vielfachen der kleinsten Zahl, die noch nicht markiert wurde, als zusammengesetzt markiert. Diese Vielfachen werden übersprungen, indem beim Aktualisieren von Zahlen Schritte der aktuellen Primzahl gemacht werden.
• Der Code stoppt, wenn Zahlen leer sind, und die Liste der gefundenen Primzahlen wird in Primzahlen zurückgegeben.

Potenzielle Probleme:

Es gibt ein potenzielles Problem bei der Implementierung, bei der die Startzahl als Primzahl markiert wird, wenn sie nur berücksichtigt werden sollte Zahlen von 2 bis n. Dies könnte behoben werden, indem die Schleife bei 2 statt bei 0 gestartet wird.

Verwendung:

Um diese Implementierung zu verwenden, können Sie die Funktion get_primes aufrufen und die gewünschte Obergrenze übergeben als Argument gebunden. Um beispielsweise alle Primzahlen bis 1000 zu finden, können Sie Folgendes verwenden:

primes = get_primes(1000)

Ausgabe:

Die Ausgabe des Codes ist eine Liste von Primzahlen Zahlen bis zur angegebenen Ganzzahl. Wenn Sie den Code beispielsweise mit n = 1000 ausführen, wird die folgende Ausgabe erzeugt:

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ..., 977]

Das obige ist der detaillierte Inhalt vonWas ist der schnellste Weg, alle Primzahlen unterhalb einer bestimmten ganzen Zahl N zu finden?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!