Bestimmen, ob eine Zahl prim ist
Ich habe eine Menge Code zu diesem Thema gelesen, aber die meisten von ihnen erzeugen die Zahlen, die bis zur Eingangsnummer prim sind. Ich benötige jedoch einen Code, der nur prüft, ob die angegebene Eingangsnummer prim ist.
Hier ist, was ich schreiben konnte, aber es funktioniert nicht:
%Vor%Ich würde mich freuen, wenn mir jemand Tipps geben könnte, wie das funktioniert.
Aktualisieren
Ich habe es geändert, um alle Zahlen in einer for-Schleife zu überprüfen.
%Vor%20 Antworten
Sie müssen noch etwas überprüfen. Im Moment überprüfen Sie nur, ob die Zahl durch 2 teilbar ist. Tun Sie dasselbe für 2, 3, 4, 5, 6, ... bis zu number . Tipp: Verwenden Sie eine Schleife .
Nachdem Sie das Problem gelöst haben, suchen Sie nach Optimierungen. Tipp: Sie müssen nur alle Zahlen bis zur Quadratwurzel der Zahl überprüfen
Meine eigene IsPrime () - Funktion, geschrieben und basierend auf der deterministischen Variante des berühmten Rabin-Miller-Algorithmus, kombiniert mit optimiertem Schritt-Brute-Forcing, bietet Ihnen eine der schnellsten Testfunktionen überhaupt.
%Vor%Um den Code zu verwenden, kopieren Sie ihn und fügen Sie ihn oben in Ihr Programm ein. Rufen Sie es auf, und es gibt einen BOOL-Wert zurück, entweder True oder False.
%Vor%Wenn Sie beim Kompilieren mit "__int64" ein Problem bekommen, ersetzen Sie dieses durch "long". Es kompiliert gut unter VS2008 und VS2010.
Wie es funktioniert: Die Funktion besteht aus drei Teilen. Teil überprüft, ob es eine der seltenen Ausnahmen (negative Zahlen, 1) ist, und abfängt die Ausführung des Programms.
Teil zwei beginnt, wenn die Zahl kleiner ist als 1373653, was die theoretische Zahl ist, bei der der Rabin-Miller-Algorithmus meine optimierte Brute-Force-Funktion übertrifft. Dann kommen zwei Stufen von Rabin Miller, um die Anzahl der benötigten Zeugen zu minimieren. Da die meisten Zahlen, die Sie testen werden, unter 4 Milliarden liegen, kann der probabilistische Rabin-Miller-Algorithmus durch Überprüfen der Zeugen 2, 7 und 61 deterministisch gemacht werden. Wenn Sie die 4 Milliarden Cap überschreiten müssen, benötigen Sie eine große number library und wendet eine modul- oder bit shift-Änderung auf die power () -Funktion an.
Wenn Sie auf einer Brute-Force-Methode bestehen, hier ist nur meine optimierte Brute-Force-IsPrime () -Funktion:
%Vor%Wie dieses Brute-Force-Stück funktioniert: Alle Primzahlen (außer 2 und 3) können in der Form 6k + 1 oder 6k-1 ausgedrückt werden, wobei k eine positive ganze Zahl ist. Dieser Code verwendet diese Tatsache und testet alle Zahlen in der Form von 6k + 1 oder 6k-1 weniger als die Quadratwurzel der fraglichen Nummer. Dieses Stück ist in meine größere IsPrime () -Funktion integriert (die Funktion zuerst).
Wenn Sie alle Primzahlen unterhalb einer Zahl finden müssen, finden Sie alle Primzahlen unter 1000, schauen Sie in das Sieb von Eratosthenes. Ein weiterer Liebling von mir.
Als zusätzliche Anmerkung würde ich gerne sehen, dass irgendjemand den Eliptical Curve Method-Algorithmus implementiert, der schon seit einiger Zeit in C ++ implementiert sein möchte. Ich habe meine Implementierung verloren. Theoretisch ist es sogar schneller als der deterministische Rabin-Miller-Algorithmus, den ich implementiert habe, obwohl ich mir nicht sicher bin, ob das für Zahlen unter 4 Milliarden gilt.
Ich nehme an, dass sqrt und foreach frpm 2 zu sqrt + 1 ausgeführt werden, wenn (input% number! = 0) false zurückgibt; Sobald Sie sqrt + 1 erreichen, können Sie sich sicher sein, dass es das Beste ist.
Wenn Sie den Bereich der Eingaben kennen (was Sie tun, da Ihre Funktion int annimmt), können Sie eine Tabelle von Primzahlen vorberechnen, die kleiner oder gleich der Quadratwurzel der maximalen Eingabe ist (2 ^ 31-1 In diesem Fall), und teste dann die Teilbarkeit, indem jede Primzahl in der Tabelle kleiner oder gleich der Quadratwurzel der angegebenen Zahl ist.
Dieser Code prüft nur, ob die Zahl durch zwei teilbar ist. Damit eine Zahl prim ist, darf sie nicht ganz durch alle ganzen Zahlen kleiner als sie selbst sein. Dies kann naiv implementiert werden, indem überprüft wird, ob es durch ganze Zahlen kleiner als floor(sqrt(n)) in einer Schleife teilbar ist. Wenn Sie interessiert sind, gibt es eine Reihe von viel schnelleren Algorithmen , die es gibt.
Wenn du faul bist und viel RAM hast, erschaffe ein Sieb von Eratosthenes , das praktisch ein riesiges Array ist aus dem du alle Zahlen gekickt hast, die nicht prim sind. Ab dann wird jeder Prime "Wahrscheinlichkeits" -Test super schnell sein. Die obere Grenze für diese Lösung für schnelle Ergebnisse ist die Menge an RAM. Die Obergrenze für diese Lösung für SuperLow-Ergebnisse ist die Kapazität Ihrer Festplatte.
Ich folge dem gleichen Algorithmus, aber einer anderen Implementierung, die zu sqrt (n) mit Schritt 2 nur ungeraden Zahlen führt, weil ich überprüfe, ob es, wenn es durch 2 oder 2 * k teilbar ist, falsch ist. Hier ist mein Code
%Vor%Benutze Mathematik zuerst die Quadratwurzel der Zahl und dann die Schleife, bis die Zahl endet, die du nach der Quadratwurzelung erhältst. überprüfe für jeden Wert, ob die gegebene Zahl durch den Iterationswert teilbar ist. Wenn irgendein Wert die gegebene Zahl teilt, dann ist es keine Primzahl, sonst Primzahl. Hier ist der Code
%Vor% Es gibt mehrere verschiedene Ansätze für dieses Problem.
Die "naive" Methode: Versuche alle (ungeraden) Zahlen bis zur (Wurzel) der Zahl.
Verbesserte "Naive" Methode: Versuche nur alle 6n ± 1.
Probabilistische Tests: Miller-Rabin, Solovay-Straße, etc.
Welcher Ansatz zu Ihnen passt, hängt davon ab, was Sie mit der Prime machen.
Sie sollten zumindest auf Primärtests nachlesen.
Wenn n 2 ist, ist es prim.
Wenn n 1 ist, ist es nicht prim.
Wenn n gerade ist, ist es nicht prim.
Wenn n ungerade ist, größer als 2, müssen wir alle ungeraden Zahlen 3..sqrt (n) +1 prüfen, wenn irgendeine dieser Zahlen n teilen kann, n ist nicht prim, sonst ist n prim.
Für bessere Leistung empfehle ich Sieb von Eratosthenes.
Hier ist das Codebeispiel:
%Vor%
Ich habe diese Idee zu finden, wenn die Nr. ist Prime oder nicht:
%Vor%