Die folgende Methode wird als “Sieb des Erathostenes” bezeichnet. Sie bestimmt alle Primzahlen unterhalb einer gegebenen Grenze n:
Algorithmus: Sieb des Erathostenes
- Schreibe alle Zahlen von 2 bis n auf.
- Markiere die Zahl 2 als Primzahl und streiche alle Vielfachen der 2.
- Finde die kleinste nicht gestrichene und nicht markierte Zahl m.
- Markiere m als Primzahl und streiche alle Vielfachen von m.
- Führe die Schritte 3-4 solange aus, bis keine Zahl m ≤ n mehr gefunden wird.
- Alle markierten Zahlen sind Primzahlen.
Lösen Sie zunächst die folgenden theoretischen Aufgaben:
- Führen Sie den Algorithmus für N=17 durch und zeichnen Sie den Verlauf tabellarisch auf.
- Terminiert der Algorithmus immer? Ist er determiniert? Ist er deterministisch? Ist er korrekt? Begründen Sie jeweils.
Implementrieren Sie dann folgende Methoden:
- boolean[] sieve(int n):
Diese soll ein Boolesches Array b der Länge n + 1 zurückliefern, das für jede Zahl k = 0, ..., n anzeigt ob es sich um eine Primzahl handelt (b[k]) ob nicht (!b[k]).
- List<Integer> primesUpTo(int n):
Es soll eine Liste aller Primzahlen kleiner n erzeugt werden.