public class Eratosthenes {


/*
* Die Obergrenze für das Sieben wird durch den Parameter grenze bestimmt.
* Ist er ungueltig (grenze < 2), so wird null zurueckgeliefert.
* grenze ist in den Test eingeschlossen, d.h. getestet wird das Intervall [2; grenze].
* Die Rueckgabe der Methode ist die Liste der „Streichungen“ als Array. Wurde die Zahl i
* gestrichen, so ist der Wert des Arrays an Stelle i gleich true.
*/
public static boolean[] siebe(int grenze) {
	if (grenze>1){
	boolean[] liste = erzeugeListe(grenze+1);
	if (grenze <= 2) {
	return liste;
	}
	int y = 2;
	while (y * y < grenze) {
	y = findeKleinsteUngestricheneZahl(y, liste);
	streicheVielfache(y, liste);
	y++;
	}return liste;} else
	return null;
	}


/*
* Diese Methode erzeugt die Liste fuer die Streichungen in der passenden Groesse
* und streicht die Zahlen 0 und 1 vorab. Fuer unzulaessige Eingaben (groesse < 2) liefert
* die Methode null zurück.
*/
public static boolean[] erzeugeListe(int groesse) {
	boolean[] liste = new boolean[groesse];
	java.util.Arrays.fill(liste,false);
	liste[0] = true;
	liste[1] = true;
	return liste;
}

/*
* Diese Methode streicht die Vielfachen der Zahl zahl bis zur Obergrenze im Array liste.
* Ist der Parameter zahl unzulaessig (zahl kleiner 1 oder zahl groesser als die Obergrenze),
* so bleibt die Liste unveraendert.
*/
public static void streicheVielfache(int zahl, boolean[] liste) {
	int i = 2;
	int x = 0;
	while (zahl * i < liste.length) {
			x = zahl * i;
			liste[x] = true;
			i = i + 1;
	}
}

/*
* Diese Methode gibt die kleinste ungestrichene Zahl in der Liste zurueck, die groeßer als beginn
* ist. Enthaelt die Liste keine solche Zahl, wird die Obergrenze zurueckgegeben, bei unzulässigen Eingaben
* ist -1 der Rückgabewert.
*/
public static int findeKleinsteUngestricheneZahl(int beginn, boolean[] liste) {
	while ((liste[beginn] != false) & (beginn<liste.length)) {
	beginn = beginn + 1;
	}
	return beginn;
	}


/*
 * main-Methode
 */
public static void main(String[] args) {
	outputPrimes(siebe(8004));
	outputPrimes(siebe(49));
	outputPrimes(siebe(2));
	outputPrimes(siebe(997));

}


/*
 * Hilfsmethode zur Ausgabe der Primzahlen
 */
private static void outputPrimes(boolean[] result) {

	if (result == null)
		return;

	for (int i = 0; i < result.length; i++) {
		if (!result[i])
			System.out.print(i + " ");
	}

	System.out.println();
}


}