/***************************  Sieb.java  **************************************/

import AlgoTools.IO;

/**  Sieb des Eratosthenes zur Ermittlung von Primzahlen.
 *   Idee: Streiche alle Vielfachen von bereits als prim erkannten Zahlen.
 */

public class Sieb {

  public static void main (String [] argv) {

    boolean[]prim;                            // boole'sches Array
    int i, j, n;                              // Laufvariablen

    n = IO.readInt("Bitte Primzahlgrenze: "); // fordere Obergrenze an
    prim = new boolean[n];                    // allokiere Speicherplatz

    for (i = 2; i < n; i++) prim[i] = true;   // alle sind zunaechst Primzahl

    for (i = 2; i < n; i++)
        if (prim[i]) {                        // falls i als Primzahl erkannt,
            IO.println(i,10);                 // gib sie aus, und 
            for (j = i+i; j < n; j = j+i)     // fuer alle Vielfachen j von i
                prim[j] = false;              // streiche j aus der Liste 
        }
  }
}