Die folgende Methode wird als “Sieb des Erathostenes” bezeichnet. Sie bestimmt alle Primzahlen unterhalb einer gegebenen Grenze n:
PROCEDURE SIEB(n)
- Schreibe alle Zahlen von 2 bis n nacheinander 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.
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.
package de.hsrm.cs.ads;
public class Sieve {
static boolean[] sieve(int n) {
boolean[] result = new boolean[n + 1];
return result;
}
static List<Integer> primesUpTo(int n){
List<Integer> result = new LinkedList<>();
return result;
}
static int[] primeFactors(int n) {
int [] result = null;
return result;
}
}
Subato
