Sieve

Die folgende Methode wird als “Sieb des Erathostenes” bezeichnet. Sie bestimmt alle Primzahlen unterhalb einer gegebenen Grenze n:

 

PROCEDURE SIEB(n)

1. Schreibe alle Zahlen von 2 bis n nacheinander auf.
2. Markiere die Zahl 2 als Primzahl und streiche alle Vielfachen der 2.
3. Finde die kleinste nicht gestrichene und nicht markierte Zahl m.
4. Markiere m als Primzahl und streiche alle Vielfachen von m.
5. Führe die Schritte 3-4 solange aus, bis keine Zahl m ≤ n mehr gefunden wird.
6. Alle markierten Zahlen sind Primzahlen.

Implementrieren Sie 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.
• int[] primeFactors(int n):
  Sie soll für eine Zahl n den Array aller Primzahlen, die als Teiler in n vorkommen, erzeugen. Gegeben z.B. die Zahl 380 = 2 * 2 * 5 * 19, sollte die Methode das Array {2, 5, 19} zurückliefern. Die Primfaktoren sollen aufsteigend sortiert sein, und jeder soll nur einmal angegeben werden.