Java: Wie funktioniert dieser Primzahlengenerator?
public static List<Integer> generateNumbers(int border) {
List<Integer> finalList = new ArrayList<>();
boolean[] bool = new boolean[border];
for (int i = 0; i < bool.length; i++) {
bool[i] = true;
}
/////////
for (int i = 2; i < Math.sqrt(border); i++) {
if (bool[i] == true) {
for (int j = (i * i); j < border; j = j + i) {
bool[j] = false;
}
}
}
////////
for (int i = 2; i < bool.length; i++) {
if (bool[i] == true) {
finalList.add(i);
}
}
return finalList;
}
Mir geht es vor allem um den Bereich, welcher in den ///////// drinnen liegt, wo ich die Nicht-Primzahlen herausfische. Kann mir jemand diese for-Schleife Schritt für Schritt erklären?
3 Antworten
Das ist das Sieb des Erathostenes. Wird an tausend und einer Stelle erklärt. Es werden alle Vielfachen von Primzahlen gestrichen, danach geht es mit der nächsten ungestrichenen Zahl weiter.
Wenn man seine Variablen i, j, bool und finalList nennt, darf man sich nicht wundern, dass der Code unverständlich ist.
Aber velleicht ist genau das Absicht, damit man sich damit auseinander setzt.
Benenne wie folgt um:
bool -> ungestrichen
i -> primzahl
j -> vielfaches
Dann sollte es kalr sein, was da passiert.
Im zweiten Schritt machst du aus ungestrichen gestrichen und drehst die Logik von false nach true
Alles kalr ! ........................ ich konnte es mir nicth verkneifen .
Aber velleicht ist genau das Absicht, damit man sich damit auseinander setzt............ gar nicht mal schlecht, sonst denkt man nur , man versteht etwas ( mit klareren Bezeichnungen )
Hallo,
https://de.wikipedia.org/wiki/Sieb_des_Eratosthenes
der fängt bei 2 an (bis Wurzel Maximun) und wirft in der inneren Schleife alle Vielfache der aktuellen Zahl raus, also für 2 fängt er bei 4 an und entfernt 4, 6, 8, etc, bei 3 fängt er bei 9 an und macht mit 12, 15, 18, etc. weiter
Es handelt sich dabei um das "Sieb des Eratosthenes". Es werden die Vielfachen der Primzahlen aus der Liste gelöscht.
Es beginnt mit i = 2
Es wird 2*2 = 4 gelöscht und dann alle weiteren Zahlen, die 2 entfernt sind. (alle geraden zahlen)
Dann wird 3*3 gelöscht (2*3 wurde zuvor schon gelöscht). und alle weiteren 3 entfernten Zahlen.
4*4 wird nicht (nochmal) gelöscht, da dies von der "Zweierreihe" schon erledigt wurde.
Es folgt 5 * 5, (2*5 und 4 * 5 wurden schon von der Zweierreihe gelöscht, 3*5 von der Dreiherreihe)
u.s.w.