/***************************  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[] sieb;                           // boole'sches Array
    int i, j, n;                              // Laufvariablen

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

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

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