Welcher ist der schnellste Algorithmus, um Primzahlen mit C++ zu finden? Ich habe das Siebverfahren verwendet, aber ich möchte immer noch, dass es schneller wird!
Eine sehr schnelle Implementierung des Sieve of Atkin ist Dan Bernsteins primegen. Dieses Sieb ist effizienter als das Sieve of Eratosthenes. Auf seiner Seite finden Sie einige Benchmark-Informationen.
Eigentlich glaube ich nicht, dass primegen das schnellste ist, oder sogar das zweitschnellste; yafu und primesieve sind im Allgemeinen schneller, denke ich, und sicherlich über 2^32. Beide sind (modifizierte) Siebe des Eratosthenes anstelle des Atkin-Bernstein-Siebs.
Primesieve Sieb des Eratosthenes (SoE) ist der schnellstmögliche Algorithmus und wird immer schneller sein als jede Implementierung des Sieb des Atkin SoA - einschließlich Bernsteins, wie in dieser Antwort verlinkt - da primesieve die Anzahl der Operationen im Vergleich zu SoA reduziert: Für den Zahlenbereich von 32 Bit (2^32 - 1) führt primesieve etwa 1,2 Milliarden Ausschlussvorgänge durch, während SoA insgesamt etwa 1,4 Milliarden kombinierte Umkehr- und quadratfreie Operationen durchführt, wobei beide Operationen ungefähr dieselbe Komplexität haben und auf ähnliche Weise optimiert werden können.
Fortsetzung: Bernstein hat nur den SoE unter Verwendung derselben effektiven Radfaktorisierung wie für den SoA verglichen, was ein 2;3;5-Rad ist, dessen Verwendung zu etwa 1,83 Milliarden Aussortierungen im 32-Bit-Zahlenbereich führt; dies macht den SoA etwa 30 % schneller, wenn man diese eingeschränkte Version des SoE vergleicht für äquivalente andere Optimierungen. Allerdings verwendet der primesieve-Algorithmus ein 2;3;5;7-Rad in Kombination mit einem 2;3;5;7;11;13;17-Rad-Segment-Vorsortierung, um die Anzahl der Operationen auf etwa 1,2 Milliarden zu reduzieren, um etwa 16,7 % schneller als SoA mit äquivalenten Optimierungen der Operationsschleife zu laufen.
Wenn es wirklich schnell gehen muss, können Sie eine Liste von Primzahlen einbeziehen:
http://www.bigprimes.net/archive/prime/
Wenn Sie nur wissen müssen, ob eine bestimmte Zahl eine Primzahl ist, gibt es verschiedene Primzahltests auf Wikipedia aufgelistet. Sie sind wahrscheinlich die schnellste Methode, um festzustellen, ob große Zahlen Primzahlen sind, insbesondere weil sie Ihnen sagen können, ob eine Zahl nicht eine Primzahl ist.
Eine Liste aller Primzahlen? Ich denke, du meinst eine Liste der ersten paar Primzahlen... :)
Bis jetzt glaube ich, dass der schnellste Primzahltestalgorithmus Strong Probable Prime (SPRP) ist. Ich zitiere aus den Nvidia CUDA Foren:
Eines der praktischeren Nischeprobleme in der Zahlentheorie hat mit der Identifizierung von Primzahlen zu tun. Gegeben N, wie können Sie effizient bestimmen, ob es eine Primzahl ist oder nicht? Dies ist nicht nur ein theoretisches Problem, es könnte ein echtes sein, das im Code benötigt wird, vielleicht wenn Sie dynamisch eine Primzahl-Hashtabellengröße innerhalb bestimmter Bereiche finden müssen. Wenn N etwa auf der Größenordnung von 2^30 liegt, möchten Sie wirklich 30000 Divisionstests durchführen, um nach Faktoren zu suchen? Offensichtlich nicht.
Die häufige praktische Lösung für dieses Problem ist ein einfacher Test namens Euler Probable Prime Test und eine leistungsstärkere Verallgemeinerung namens Strong Probable Prime (SPRP). Dies ist ein Test, der für eine ganze Zahl N probabilistisch als prim oder nicht klassifizieren kann, und wiederholte Tests können die Korrektheitswahrscheinlichkeit erhöhen. Der langsame Teil des Tests selbst besteht hauptsächlich darin, einen Wert ähnlich wie A^(N-1) modulo N zu berechnen. Jeder, der RSA-Public-Key-Verschlüsselungsvarianten implementiert hat, hat diesen Algorithmus verwendet. Er ist nützlich sowohl für große ganze Zahlen (wie 512 Bit) als auch normale 32 oder 64 Bit-Integers.
Der Test kann von einer probabilistischen Ablehnung in einen definitiven Beweis für Primzahlverhältnisse umgewandelt werden, indem bestimmte Testeingabeparameter vorberechnet werden, die bekannt sind, um für Bereiche von N immer erfolgreich zu sein. Leider ist die Entdeckung dieser "besten bekannten Tests" effektiv die Suche nach einem riesigen (in der Tat unendlichen) Bereich. 1980 wurde eine erste Liste nützlicher Tests von Carl Pomerance erstellt (berühmt dafür, derjenige zu sein, der RSA-129 mit seinem quadratischen Siebalgorithmus faktorisieren konnte). Später verbesserte Jaeschke die Ergebnisse signifikant im Jahr 1993. 2004 verbesserten Zhang und Tang die Theorie und Grenzen des Suchbereichs. Greathouse und Livingstone haben bis jetzt die modernsten Ergebnisse im Web veröffentlicht, unter http://math.crg4.com/primes.html, die besten Ergebnisse eines riesigen Suchbereichs.
Weitere Informationen finden Sie hier: http://primes.utm.edu/prove/prove2_3.html und http://forums.nvidia.com/index.php?showtopic=70483
Wenn Sie einfach eine Möglichkeit benötigen, sehr große Primzahlen zu erzeugen und sich nicht darum kümmern, alle Primzahlen < als eine ganze Zahl n zu erzeugen, können Sie den Lucas-Lehmer-Test verwenden, um Mersenne-Primzahlen zu überprüfen. Eine Mersenne-Primzahl ist in der Form von 2^p -1. Ich denke, dass der Lucas-Lehmer-Test der schnellste Algorithmus ist, der für Mersenne-Primzahlen entdeckt wurde.
Und wenn Sie nicht nur den schnellsten Algorithmus verwenden möchten, sondern auch die schnellste Hardware, versuchen Sie, ihn mit Nvidia CUDA zu implementieren, schreiben Sie einen Kernel für CUDA und führen Sie ihn auf der GPU aus.
Sie können sogar etwas Geld verdienen, wenn Sie große genug Primzahlen entdecken, EFF vergibt Preise von $50K bis $250K: https://www.eff.org/awards/coop
Es gibt einen 100% mathematischen Test, der überprüft, ob eine Zahl P prim oder zusammengesetzt ist, genannt AKS Primality Test.
Das Konzept ist einfach: Gegeben eine Zahl P, wenn alle Koeffizienten von (x-1)^P - (x^P-1) durch P teilbar sind, dann ist P eine Primzahl, ansonsten ist es eine zusammengesetzte Zahl.
Zum Beispiel, gegeben P = 3, würde das Polynom ergeben:
(x-1)^3 - (x^3 - 1)
= x^3 + 3x^2 - 3x - 1 - (x^3 - 1)
= 3x^2 - 3xUnd die Koeffizienten sind beide durch 3 teilbar, daher ist die Zahl prim.
Ein Beispiel, wo P = 4, was KEINE Primzahl ist, würde ergeben:
(x-1)^4 - (x^4-1)
= x^4 - 4x^3 + 6x^2 - 4x + 1 - (x^4 - 1)
= -4x^3 + 6x^2 - 4xUnd hier sehen wir, dass der Koeffizient 6 nicht durch 4 teilbar ist, daher ist es NICHT prim.
Das Polynom (x-1)^P wird P+1 Terme haben und kann mit Kombination gefunden werden. Daher wird dieser Test in O(n) Laufzeit ausgeführt, daher weiß ich nicht, wie nützlich dies wäre, da man einfach über i von 0 bis p iterieren und auf den Rest prüfen kann.
AKS ist in der Praxis eine sehr langsame Methode, die nicht mit anderen bekannten Methoden konkurriert. Die Methode, die Sie beschreiben, ist nicht AKS, sondern ein Eröffnungslemma, das langsamer ist als die nicht optimierte Probeteilung (wie Sie herausstellen).
Hallo @Kousha, wofür steht das x in (x-1)^P - (x^P-1)? Haben Sie einen Beispielcode dafür? In C++ zur Bestimmung, ob die Zahl eine Primzahl ist oder nicht?
@kiLLua X ist nur eine Variable. Es ist der Koeffizient von X, der bestimmt, ob die Zahl prim ist oder nicht. Und nein, ich habe den Code nicht. Ich empfehle nicht wirklich, diese Methode tatsächlich zu verwenden, um festzustellen, ob eine Zahl prim ist oder nicht. Dies ist nur ein sehr cooles mathematisches Verhalten von Primzahlen, aber ansonsten ist es unglaublich ineffizient.
Ist Ihr Problem zu entscheiden, ob eine bestimmte Zahl eine Primzahl ist? Dann benötigen Sie einen Test auf Primzahlen (einfach). Oder benötigen Sie alle Primzahlen bis zu einer bestimmten Zahl? In dem Fall sind Primzahl-Siebe gut (einfach, erfordern aber Speicherplatz). Oder benötigen Sie die Primfaktoren einer Zahl? Dies würde eine Faktorisierung erfordern (schwierig für große Zahlen, wenn Sie wirklich die effizientesten Methoden möchten). Wie groß sind die Zahlen, mit denen Sie arbeiten? 16 Bits? 32 Bits? Größer?
Ein cleverer und effizienter Weg ist es, Tabellen von Primzahlen vorzuberechnen und sie in einer Datei mit einer Codierung auf Bit-Ebene zu speichern. Die Datei wird als ein langer Bitvektor betrachtet, wobei das Bit n die Zahl n darstellt. Wenn n eine Primzahl ist, wird sein Bit auf eins gesetzt und sonst auf null. Die Suche ist sehr schnell (Sie berechnen den Byte-Offset und eine Bit-Maske) und erfordert nicht, dass die Datei im Speicher geladen wird.
CodeJaeger ist eine Gemeinschaft für Programmierer, die täglich Hilfe erhalten..
Wir haben viele Inhalte, und Sie können auch Ihre eigenen Fragen stellen oder die Fragen anderer Leute lösen.
0 Stimmen
Ein altes Artikel, das ich gefunden habe, aber interessant aussieht: Spaß mit Primzahlen
30 Stimmen
@Jaider dies scheitert bereits bei Zahlen so niedrig wie 7 (111). Es scheitert auch für 1001=9. Und offensichtlich scheitert es für fast alle Primzahlen im Allgemeinen (deckt nicht den Fall 2^p - 1 ab, die Mersenne-Primzahlen sind - klassisch generierte Beispiele - die immer in Form von 111...1 sein werden)
2 Stimmen
@Kasperasky - Sie haben nicht erwähnt, welches Sieb? Sie meinen wahrscheinlich das Sieb von Eranthoses!
0 Stimmen
Sieb des Eratosthenes Algorithmus
1 Stimmen
Es ist erstaunlich zu sehen, wie viele Antworten es gibt, wenn die Frage absolut unmöglich zu beantworten ist, ohne den Zahlenbereich zu kennen, der abgedeckt werden soll. Wenn Sie alle Primzahlen möchten, ist kein schneller Algorithmus erforderlich.
0 Stimmen
@YvesDaoust ... und mit der besten Antwort, die eindeutig falsch ist, und der zweitbesten Antwort, die keine Antwort ist (im Grunde genommen sagt sie: "Jemand anderes hat es bereits gemacht, nutze ihre Ergebnisse").
1 Stimmen
@WillNess: Würde
int p[]= {2, 3};als "schnellster Algorithmus zum Auffinden von Primzahlen" gelten?0 Stimmen
@YvesDaoust "...unter 4", vielleicht (mit der fest codierten 4). Andernfalls muss der benötigte Bereich angegeben werden (auch wenn es [0,+inf) ist).
1 Stimmen
@WillNess: Ich frage mich, ob eine einzige Primzahl ausreichen würde, um "numberS" zu befriedigen.
0 Stimmen
@YvesDaoust auch keine Zahlen können die Antwort sein, zum Beispiel für Primzahlen über 5 unter 7.