Primzahleniterator gibt hohe Zahlen nicht aus

Mhm, mir ist der Algorithmus zu kompliziert und mir reicht mein primitiver Ansatz… Ich finde auch, der Pseudocode auf Wikipedia ist „zu weit vom realen Code entfernt“.

Ich Banause. :wink:

Aus praktischer Sicht ist die mikroskopische Fehlerwahrscheinlichkeit bei Tests wie Miller-Rabin vernachlässigbar, und für fast alle Anwendungen die beste Lösung (deshalb ist es in BigInteger so implementiert). Um diese winzige Unsicherheit wegzubekommen, muss man schwere Geschütze wie AKS auffahren. Deine Lösung mag eine gute Übung zur Parallelisierung sein, aus Performancegründen ist sie jenseits der long-Range völlig unpraktisch - wobei du nicht einmal mit einem schnelleren „ungenauen“ Verfahren fast alle zusammengesetzten Zahlen vorher aussortierst.

Übrigens gibt es noch eine einfache Optimierung, um die Teilbarkeit durch mehrere Zahlen gleichzeitig testen zu können: Du kannst ein BigInteger p des Produkts 2 * 3 * 5 * 7 *…*P erstellen, und dann schauen, ob für deinen Kandidaten k mit k > P die Bedingung k.gcd ( p ) == 1 gilt, ansonsten ist k durch eine der Primzahlen im Produkt teilbar. Natürlich müssen größere Primzahlen dann wie gewohnt weiter getestet werden.