Welcher ist der schnellste Algorithmus, um Primzahlen zu finden?

Welcher ist der schnellste Algorithmus, um Primzahlen mit C ++ zu finden? Ich habe Sieb-Algorithmus verwendet, aber ich möchte immer noch schneller sein!

Eine sehr schnelle Umsetzung des Siebes von Atkin ist Dan Bernsteins Hauptquelle . Dieses Sieb ist effizienter als das Sieb von Eratosthenes . Seine Seite enthält einige Benchmark-Informationen.

Wenn es wirklich schnell sein muss, können Sie eine Liste von Primzahlen hinzufügen:
http://www.bigprimes.net/archive/prime/

Wenn Sie nur wissen müssen, ob es sich bei einer bestimmten Zahl um eine Primzahl handelt, werden in Wikipedia verschiedene Primärtests aufgelistet . Sie sind wahrscheinlich die schnellste Methode, um zu bestimmen, ob große Zahlen Primzahlen sind, vor allem, weil sie Ihnen sagen können, ob eine Zahl eine Primzahl ist.

Er, er weiß, ich bin ein Nekromant, der auf alte Fragen antwortet, aber ich habe gerade diese Frage im Netz nach Möglichkeiten gefunden, effiziente Primzahltests zu implementieren.

Bis jetzt glaube ich, dass der schnellste Primzahl-Testalgorithmus Strong Probable Prime (SPRP) ist. Ich zitiere aus Nvidia CUDA Foren:

Eines der praktischeren Nischenprobleme in der Zahlentheorie hat mit der Identifizierung von Primzahlen zu tun. Mit N, wie können Sie effizient bestimmen, ob es prim ist oder nicht? Dies ist nicht nur ein theoretisches Problem, es kann ein reales sein, das im Code benötigt wird, vielleicht, wenn Sie dynamisch eine Primzahl-Hashtabellengröße innerhalb bestimmter Bereiche finden müssen. Wenn N etwas in der Größenordnung von 2 ^ 30 ist, wollen Sie wirklich 30000 Divisions-Tests durchführen, um nach irgendwelchen Faktoren zu suchen? Offensichtlich nicht.

Die übliche praktische Lösung für dieses Problem ist ein einfacher Test, der als Euler-wahrscheinlicher-Primärtest bezeichnet wird, und eine stärkere Generalisierung, die als Strong Probable Prime (SPRP) bezeichnet wird. Dies ist ein Test, der für eine ganze Zahl N probabilistisch als Primzahl klassifizieren kann oder nicht, und wiederholte Tests können die Korrektheitswahrscheinlichkeit erhöhen. Der langsame Teil des Tests selbst beinhaltet meistens die Berechnung eines Werts ähnlich A ^ (N-1) Modulo N. Jeder, der RSA Public-Key-Verschlüsselungsvarianten implementiert, hat diesen Algorithmus verwendet. Es ist sowohl für große Ganzzahlen (wie 512 Bit) als auch für normale 32 oder 64 Bit nützlich.

Der Test kann von einer probabilistischen Zurückweisung in einen definitiven Primzahlbeweis geändert werden, indem bestimmte Testeingabeparameter vorberechnet werden, von denen bekannt ist, dass sie für Bereiche von N immer erfolgreich sind. Leider ist die Entdeckung dieser “bekanntesten Tests” effektiv eine Suche nach einem großen ( in der Tat unendlich) Domäne. Im Jahr 1980 wurde eine erste Liste von nützlichen Tests von Carl Pomerance erstellt (berühmt dafür, RSA-129 mit seinem Quadratic Seive-Algorithmus zu berücksichtigen). Später verbesserte Jaeschke die Ergebnisse 1993 erheblich. Im Jahr 2004 verbesserten Zhang und Tang die Theorie und Grenzen der Suchdomäne. Greathouse und Livingstone haben die aktuellsten Ergebnisse im Internet veröffentlicht, unter http://math.crg4.com/primes.html , den besten Ergebnissen einer riesigen Such-Domain.

Siehe hier für weitere Informationen: http://primes.utm.edu/prove/prove2_3.html und http://forums.nvidia.com/index.php?showtopic=70483

Wenn Sie nur einen Weg brauchen, um sehr große Primzahlen zu erzeugen und nicht alle Primzahlen

Und wenn Sie nicht nur den schnellsten Algorithmus, sondern auch die schnellste Hardware verwenden wollen, versuchen Sie, ihn mit Nvidia CUDA zu implementieren, schreiben Sie einen coreel für CUDA und führen Sie ihn auf GPU aus.

Sie können sogar Geld verdienen, wenn Sie genug Primzahlen entdecken, EFF gibt Preise von $ 50.000 bis $ 250.000: https://www.eff.org/awards/coop

Es gibt einen 100% mathematischen Test, der überprüft, ob eine Zahl P Primzahl ist oder nicht, genannt AKS Primalitätstest .

Das Konzept ist einfach: Wenn alle Koeffizienten von (x-1)^P - (x^P-1) durch eine Zahl P , dann ist P eine Primzahl, andernfalls ist es eine zusammengesetzte Zahl.

Zum Beispiel, gegeben P = 3 , würde das Polynom geben:

  (x-1)^3 - (x^3 - 1) = x^3 + 3x^2 - 3x - 1 - (x^3 - 1) = 3x^2 - 3x 

Und die Koeffizienten sind beide durch 3 teilbar, daher ist die Zahl prim.

Und ein Beispiel, wo P = 4 , was NICHT ein Prim 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 - 4x 

Und hier können wir sehen, dass der Koeffizient 6 nicht durch 4 teilbar ist, daher ist es NICHT prim.

Das Polynom (x-1)^P wird P+1 Terme und kann durch Kombination gefunden werden. Also wird dieser Test in O(n) Laufzeit laufen, also weiß ich nicht, wie nützlich das sein würde, da Sie einfach über i von 0 bis p iterieren und den Rest testen können.

Ist Ihr Problem zu entscheiden, ob eine bestimmte Zahl prim ist? Dann brauchst du einen Primzahltest (einfach). Oder brauchst du alle Primzahlen bis zu einer bestimmten Nummer? In diesem Fall sind Hauptsiebe gut (leicht, erfordern aber Speicher). Oder brauchst du die Primfaktoren einer Zahl? Dies würde eine Faktorisierung erfordern (schwierig für große Zahlen, wenn Sie wirklich die effizientesten Methoden wollen). Wie groß sind die Zahlen, die Sie betrachten? 16 Bits? 32 Bits? größer?

Ein kluger und effizienter Weg besteht darin, Primzahl-Tabellen vorzuberechnen und sie mit einer Bit-Level-Codierung in einer Datei zu speichern. Die Datei wird als ein langer Bitvektor betrachtet, während Bit n die ganze Zahl n darstellt. Wenn n prim ist, wird sein Bit auf Eins gesetzt und andernfalls auf Null. Die Suche ist sehr schnell (Sie berechnen den Byte-Offset und eine Bitmaske) und müssen nicht in den Speicher geladen werden.

Es hängt von Ihrer Anwendung ab. Es gibt einige Überlegungen:

  • Brauchen Sie nur die Information, ob einige Zahlen Primzahlen sind, ob Sie alle Primzahlen bis zu einer bestimmten Grenze benötigen oder ob Sie (möglicherweise) alle Primzahlen benötigen?
  • Wie groß sind die Zahlen, mit denen Sie umgehen müssen?

Die Miller-Rabin und Analog-Tests sind nur schneller als ein Sieb für Zahlen über einer bestimmten Größe (irgendwo um einige Millionen, glaube ich). Darunter ist eine Testabteilung (wenn Sie nur ein paar Zahlen haben) oder ein Sieb schneller.

Rabin-Miller ist ein standardisierter probabilistischer Primzahltest. (Sie führen es K-mal und die Eingabe-Nummer ist entweder definitiv zusammengesetzt, oder es ist wahrscheinlich prim mit der Wahrscheinlichkeit des Fehlers 4 -K . (ein paar hundert Iterationen und es ist fast sicher, dass Sie die Wahrheit sagen)

Es gibt eine nicht-probabilistische (deterministische) Variante von Rabin Miller .

Die Great Internet Mersenne Prime Search (GIMPS), die den weltweit größten nachgewiesenen Prime (2 74.207.281 – 1 Stand Juni 2017) gefunden hat, verwendet mehrere Algorithmen , aber diese sind Primzahlen in speziellen Formen. Die obige GIMPS-Seite enthält jedoch einige allgemeine deterministische Primzahltests. Sie scheinen zu zeigen, welcher Algorithmus “am schnellsten” ist, hängt von der Größe der zu testenden Zahl ab. Wenn Ihre Nummer in 64 Bits passt, sollten Sie wahrscheinlich keine Methode verwenden, die an Primzahlen von mehreren Millionen Ziffern arbeiten soll.

Ich verwende diese Methode immer zur Berechnung von Primzahlen, die mit dem Siebalgorithmus folgen.

 void primelist() { for(int i = 4; i < pr; i += 2) mark[ i ] = false; for(int i = 3; i < pr; i += 2) mark[ i ] = true; mark[ 2 ] = true; for(int i = 3, sq = sqrt( pr ); i < sq; i += 2) if(mark[ i ]) for(int j = i << 1; j < pr; j += i) mark[ j ] = false; prime[ 0 ] = 2; ind = 1; for(int i = 3; i < pr; i += 2) if(mark[ i ]) ind++; printf("%d\n", ind); } 
 #include main() { long long unsigned x,y,b,z,e,r,c; scanf("%llu",&x); if(x<2)return 0; scanf("%llu",&y); if(y0)z=3; } if(e==0) { printf("|%llu",z); r+=1; } } printf("|\n%llu outputs...\n",r); scanf("%llu",&r); } 
 #include  using namespace std; int set [1000000]; int main (){ for (int i=0; i<1000000; i++){ set [i] = 0; } int set_size= 1000; set [set_size]; set [0] = 2; set [1] = 3; int Ps = 0; int last = 2; cout < < 2 << " " << 3 << " "; for (int n=1; n<10000; n++){ int t = 0; Ps = (n%2)+1+(3*n); for (int i=0; i==i; i++){ if (set [i] == 0) break; if (Ps%set[i]==0){ t=1; break; } } if (t==0){ cout << Ps << " "; set [last] = Ps; last++; } } //cout << last << endl; cout << endl; system ("pause"); return 0; } 

Ich weiß, dass es etwas später ist, aber das könnte für Leute nützlich sein, die von Suchanfragen hierher kommen. Wie auch immer, hier ist etwas JavaScript, das auf der Tatsache beruht, dass nur Primfaktoren getestet werden müssen, so dass die früheren Primzahlen, die durch den Code generiert werden, als Testfaktoren für spätere verwendet werden. Natürlich werden alle even- und mod 5-Werte zuerst herausgefiltert. Das Ergebnis wird im Array P sein, und dieser Code kann 10 Millionen Primzahlen in weniger als 1,5 Sekunden auf einem i7 PC (oder 100 Millionen in etwa 20) knacken. In C neu geschrieben sollte es sehr schnell sein.

 var P = [1, 2], j, k, l = 3 for (k = 3 ; k < 10000000 ; k += 2) { loop: if (++l < 5) { for (j = 2 ; P[j] <= Math.sqrt(k) ; ++j) if (k % P[j] == 0) break loop P[P.length] = k } else l = 0 } 
 #include using namespace std; void main() { int num,i,j,prime; cout< <"Enter the upper limit :"; cin>>num; cout< <"Prime numbers till "<