Sieb des Eratosthenes
Mit dem Sieb des Eratosthenes können alle Primzahlen von zwei bis zu einer vorgegebenen Obergrenze herausgefiltert werden. In Java lässt sich dieser Algorithmus leicht implementieren.
Der Algorithmus kommt vollständig ohne jede Division aus. Dafür benötigt er allerdings für jede zu prüfende Zahl einen Speicherplatz (also mindestens ein Bit). Die einfache Implementierung unten verwendet den Datentyp boolean, was bei einer sehr großen Prüfmenge allerdings sehr ineffizient ist. Dafür bleibt die Implementierung einfach zu verstehen.
Arbeitsweise
Für jede zu prüfende Zahl wird ein Speicherplatz reserviert, in dem hinterlegt wird, ob eine Zahl prim ist oder nicht. Zur Initialisierung wird zunächst davon ausgegangen, daß jede Zahl eine Primzahl wäre. Mit dem folgenden Verfahren werden nun alle nicht-Primzahlen identifiziert und als solche markiert. Übrig bleiben sodann die Primzahlen.
Beginnend mit der kleinsten Zahl (die zwei - kleinere Zahlen werden nicht betrachtet) wird zunächst geprüft, ob sie als Primzahl markiert ist. Wenn ja, dann ist es tatsächlich eine, und es werden sogleich alle ganzzahligen Vielfachen dieser Zahl als nicht-Primzahl markiert. Im ersten Schritt wird also festgestellt, daß zwei eine Primzahl ist, und die Zahlen vier, sechs, acht, zehn, zwölf usw. werden als nicht-Primzahlen markiert.
Nun ist die nächste Zahl an der Reihe: die drei. Auch diese ist noch als Primzahl markiert und ist folglich auch eine. Also werden sogleich alle ganzzahligen Vielfachen der drei als nicht-Primzahl markiert: sechs, neun, zwölf, fünfzehn usw. sind alle nicht prim.
Nun ist die vier an der Reihe: diese wurde schon als nicht prim markiert (weil sie ein vielfaches von zwei ist) und erfordert keinen weiteren Arbeitsschritt.
Die fünf wiederum ist eine Primzahl, so daß nun alle vielfachen der fünf als nicht prim markiert werden.
Dies wird immer so wiederholt, bis zur Quadratwurzel der Obergrenze.
Primzahlen mit dem Sieb des Eratosthenes
/**
* Zahlen von zwei bis zu einer Obergrenze nach Primzahlen durchsuchen.
* Algorithmus: Sieb des Eratosthenes.
*/
public static boolean[] getPrimzahlen(int maxValue) {
if (maxValue < 2) {
maxValue = 2;
}
boolean[] isPrim = new boolean[maxValue + 1];
for (int i = maxValue; i >= 2; i--) { // mit true initialisieren
isPrim[i] = true;
}
for (int i = 2; i * i <= maxValue; i++) {
if (isPrim[i]) {
int nextNotPrim = i+i;
while (nextNotPrim <= maxValue) {
isPrim[nextNotPrim] = false;
nextNotPrim += i;
}
}
}
return isPrim;
}
Ein ähnlicher Artikel zeigt, wie man eine einzelne Zahl auf ihre Primzahleigenschaft überprüfen kann.
| Nach oben, Inhaltsverzeichnis, Impressum |
Admin: Artikel editieren |