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) {
        if(groesse > 2) {
            boolean[] liste = new boolean[groesse];
            java.util.Arrays.fill(liste, false);
            liste[0] = true;
            liste[1] = true;
            return liste;
        } else {
            boolean[] liste = new boolean[groesse];
            java.util.Arrays.fill(liste, 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(erzeugeListe(1));

    }


    /*
     * 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();
    }


}