Die Liste der Primzahlen in kürzester Zeit finden

Das Gute in Ihrem Primzahltest ist, dass Sie nur durch Primzahlen dividieren.

Das Schlimme ist, dass du durch alle Primzahlen dividierst, das heißt, alle Primzahlen sind kleiner als der Kandidat. Das bedeutet, dass Sie für den größten Prime unter einer Million, 999983, durch 78497 Primzahlen dividieren, um herauszufinden, dass diese Zahl eine Primzahl ist. Das ist eine Menge Arbeit. So viel tatsächlich, dass die Arbeit, die auf Primzahlen in diesem Algorithmus ausgegeben wird, ungefähr 99.9% aller Arbeit ausmacht, wenn man zu einer Million geht, ein größerer Teil für höhere Grenzen. Und dieser Algorithmus ist fast quadratisch, um auf diese Weise die Primzahlen auf n zu finden, müssen Sie etwa

Divisionen.

Eine einfache Verbesserung besteht darin, die Teilung früher zu stoppen. Lassen Sie n eine zusammengesetzte Zahl sein (d. H. Eine Zahl größer als 1, die andere Teiler als 1 und n hat), und d sei ein Teiler von n .

Nun, d ist ein Teiler von n bedeutet, dass n/d eine ganze Zahl ist, und auch ein Teiler von n : n/(n/d) = d . Also können wir natürlich die Teiler von n zu Paaren gruppieren, jeder Teiler d ergibt das Paar (d, n/d) .

Für ein solches Paar gibt es zwei Möglichkeiten:

1. d = n/d , was n = d² oder d = √n bedeutet.
2. Die beiden sind verschieden, dann ist einer von ihnen kleiner als der andere, sagen wir d < n/d . Aber das heißt sofort d² < n oder d < √n .

Also, in jedem Fall enthält jedes Divisor-Paar (mindestens) eins, das nicht √n überschreitet, daher wenn n eine zusammengesetzte Zahl ist, sein kleinster Divisor (anders als 1)% nicht überschreitet co_de% .

Damit können wir die Testdivision stoppen, wenn wir √n erreicht haben:

Hinweis: Das hängt von der Liste der Primzahlen ab, die in aufsteigender Reihenfolge iteriert werden. Wenn das nicht von der Sprache garantiert wird, müssen Sie eine andere Methode verwenden, indem Sie nach einem √n oder ähnlichem iterieren.

Wenn wir die Probenteilung auf der Quadratwurzel des Kandidaten beenden, für die größte Primzahl unter einer Million, 999983, müssen wir sie jetzt nur noch durch die 168 Primzahlen unter 1000 teilen. Das ist viel weniger Arbeit als vorher. Stoppen der Test-Division auf der Quadratwurzel, und nur durch Primzahlen zu teilen, ist so gut wie Test-Division möglicherweise erhalten und erfordert etwa

Divisionen, für ArrayList , das ist ein Faktor von etwa 750, nicht schlecht, oder?

Aber das ist immer noch nicht sehr effizient, die effizientesten Methoden, um alle Primzahlen unter n = 1000000 zu finden, sind Siebe. Einfach zu implementieren ist das klassische Sieb von Eratosthenes . Das findet die Primzahlen unter n in O (n * log log n) -Operationen, mit einigen Verbesserungen (Eliminierung von Vielfachen mehrerer kleiner Primzahlen aus der Betrachtung im Voraus), seine Komplexität kann auf O (n) -Operationen reduziert werden. Ein relativ neues Sieb mit besserem asymptotischem Verhalten ist das Sieb von Atkin , das die Primzahlen zu n in O (n ) Operationen oder mit der Verbesserung der Beseitigung der Vielfachen einiger kleiner Primzahlen in O (n / log log n) Operationen. Das Sieb von Atkin ist komplizierter zu implementieren, daher ist es wahrscheinlich, dass eine gute Implementierung eines Siebs von Eratosthenes besser abschneidet als eine naive Implementierung eines Siebes von Atkin. Für Implementierungen von ähnlichen Optimierungsebenen ist der Leistungsunterschied gering, es sei denn, das Limit wird groß (größer als 10 ; und es ist nicht ungewöhnlich, dass in der Praxis ein Sieb von Eratosthenes besser skaliert als ein Sieb von Atkin darüber hinaus aufgrund besserer Speicherzugriffsmuster). Also würde ich empfehlen, mit einem Sieb von Eratosthenes zu beginnen, und nur wenn seine Leistung trotz ehrlicher Optimierungsbemühungen nicht zufriedenstellend ist, tauchen Sie ein in das Sieb von Atkin. Oder, wenn Sie es nicht selbst implementieren möchten, finden Sie eine gute Implementierung, die jemand anderes bereits ernsthaft abgestimmt hat.

Ich bin in eine Antwort mit einer etwas anderen Einstellung, in der das Problem darin bestand, die n-te Primzahl. Einige Implementierungen von mehr oder weniger effizienten Methoden sind von dieser Antwort verbunden, insbesondere eine oder zwei verwendbare (wenn auch nicht sehr optimierte) Implementierungen eines Sievers von Eratosthenes.

Ich benutze immer Eratosthenes Sieb:

Ich hoffe, Sie verstehen meine Kommentare

Ich verstehe eine Primzahl als eine Zahl, die nur durch sich selbst und die Zahl 1 (ohne Rest) teilbar ist. Siehe Wikipedia-Artikel

Davon abgesehen verstehe ich den Algorithmus im zweiten Kommentar nicht sehr gut, aber eine kleine Verbesserung Ihres Algorithmus wäre, Ihre for-Schleife zu ändern:

Dies basiert auf der Annahme, dass 1, 2 und 3 Primzahlen sind und alle geraden Zahlen danach keine Primzahlen sind. Dies halbiert zumindest den Algorithmus.

Ich möchte eine noch etwas verbesserte Version zu der oben von Benjamin Oman vorgeschlagenen Version machen, Dies ist nur eine Modifikation, um zu vermeiden, dass die Primzahl aller Zahlen mit der Endziffer "5" geprüft wird, da diese Zahlen sicherlich keine Primzahlen sind, da diese durch 5 teilbar sind.

Dies basiert auf der Annahme, dass 2,3,5 Primzahlen sind. Die obige kleine Änderung wird alle Faktoren von 5 reduzieren und verbessern.