Bei der Primzahlprüfung in Java wird die Effizienz der herkömmlichen Methode, die alle Zahlen von 2 bis n-1 durchteilt, verbessert, indem nur bis sqrt(n) geprüft und das 6k±1-Muster verwendet wird.
Durch die Verwendung von Streams kann Lazy Evaluation angewendet werden, wodurch ein Stream generiert wird, der Primzahlen nur dann berechnet, wenn sie benötigt werden.
Die vorgestellten Verbesserungen und die Verwendung von Streams ermöglichen eine effizientere Implementierung des Primzahlprüfungsalgorithmus.
Um zu überprüfen, ob n eine Primzahl ist, wird üblicherweise geprüft, ob n durch Zahlen von 2 bis n - 1 teilbar ist.
In dieser Methode können wir einige Optimierungen anwenden, um sie effizienter zu machen und Lazy Evaluation mit Streams zu verwenden.
Naive Methode
Dies ist eine naive Methode, um zu überprüfen, ob n eine Primzahl ist.
Verbesserungen
Wenn n = a x b ist, können wir ohne Verlust der Allgemeinheit annehmen, dass a > b ist. Das heißt, wir müssen i nur bis sqrt(n) überprüfen. Da die sqrt()-Operation teuer ist, kann sie durch die Bedingung i * i <= n ersetzt werden.
Primzahlen größer als 5 haben die Form 6k ± 1. Daher können wir die Anzahl der Überprüfungen reduzieren, indem wir i in Schritten von 6 erhöhen.
Verbesserte Methode
Lazy Evaluation mit Streams anwenden
Streams in Java führen Operationen nicht sofort aus, wie es bei Listen der Fall ist.
Sie warten, bis eine bestimmte Operation definiert ist, und führen nur die Berechnungen für das benötigte Element aus, wenn es angefordert wird.
Mit dieser Eigenschaft können wir einen Stream erstellen, der Primzahlen generiert.