Gibt es eine Bibliotheksfunktion, die die Primzahlen (in der Reihenfolge) in Python aufzählen kann?
Ich fand diese Frage Schnellste Möglichkeit, alle aufzulisten Primzahlen unter N , aber ich würde lieber die zuverlässige Bibliothek von jemand anderem benutzen als meine eigene. Ich würde gerne import math; for n in math.primes:
Die Bibliothek gmpy2 verfügt über die Funktion next_prime (). Diese einfache Funktion erzeugt einen Generator, der unendlich viele Primzahlen liefert:
%Vor%Wenn Sie wiederholt nach Primzahlen suchen, wird das Erstellen und Wiederverwenden einer Tabelle mit allen Primzahlen unterhalb einer vernünftigen Grenze (sagen wir 1.000.000) schneller sein. Hier ist ein weiteres Beispiel, das gmpy2 und das Sieb von Eratosthenes verwendet, um eine Tabelle mit Primzahlen zu erstellen. primes2 () gibt Primzahlen zuerst aus der Tabelle zurück und verwendet dann next_prime ().
%Vor%Sie können table_limit an Ihre Bedürfnisse anpassen. Größere Werte benötigen mehr Speicher und erhöhen die Startzeit für den ersten Aufruf von primes (), sind aber für wiederholte Aufrufe schneller.
Hinweis: Ich bin der Betreuer von gmpy2.
SymPy ist eine andere Wahl. Es ist eine Python-Bibliothek für symbolische Mathematik. Es bietet mehrere Funktionen für Prime.
%Vor%Hier sind einige Beispiele.
%Vor%Seit ich diese Frage gestellt habe, habe ich einen Python-Wrapper rund um den C ++ - Bibliotheks-Primitiv geschrieben. Ссылка
%Vor%Es gibt keinen konstanten Zeitalgorithmus, um die nächste Primzahl zu erzeugen; Aus diesem Grund benötigen die meisten Bibliotheken eine obere Grenze. Dies ist ein großes Problem, das für die digitale Kryptographie gelöst werden muss. RSA wählt ausreichend große Primzahlen aus, indem eine Zufallszahl ausgewählt und auf Primalität getestet wird, bis eine Primzahl gefunden wird.
Eine beliebige Ganzzahl N vorausgesetzt, ist die einzige Möglichkeit, die nächste Primzahl nach N zu finden, die Iteration durch N+1 zur unbekannten Primzahl P , die auf Primalität testet.
Das Testen auf Primalität ist sehr billig und es gibt Python-Bibliotheken, die dies tun: AKS Primes-Algorithmus in Python
Gegeben eine Funktion test_prime , dann sieht ein unendlicher Primzahl-Iterator ungefähr wie folgt aus:
Es gibt eine Menge Heuristiken, mit denen Sie den Prozess beschleunigen können. Zum Beispiel, überspringen Sie gerade Zahlen oder Zahlen, die durch 2,3,5,7,11,13 usw. teilbar sind.
Tags und Links python