/* Auteur: Nicolas JANEY          */
/* nicolas.janey@univ-fcomte.fr   */
/* Fevrier 2005                   */

public class CribleEratostheneEnConsole {

  /* Fonction d'affichage d'un tableau de booleen         */
  /* La valeur de i est affichee si l'element d'indice i  */
  /* est a vrai                                           */
  /* t : tableau de booleen a afficher                    */

  public static void afficheTableau(boolean [] t) {
    for ( int i = 0 ; i < t.length ; i++ )
      if ( t[i] )
        Console.out.println(i);
  }

  /* Fonction de realisation du crible d'eratosthene      */
  /* pour determiner tous les nombres premiers            */
  /* inferieurs ou egaux a une valeur entiere positive    */
  /* n : entier                                           */
  /* t : tableau de booleen a remplir                     */

  public static void cribleEratosthene(int n,boolean [] t) {
  /* Initialisation a faux de t[0] et t[1]                */
  /* 0 et 1 ne sont pas des nombres premiers              */
    t[0] = false;
    t[1] = false;
  /* Initialisation a vari du reste de t                  */
  /* Pour l'instant tous les autres nombres sont          */
  /* succeptibles d'etre premier                          */
    for ( int i = 2 ; i < t.length ; i++ ) {
      t[i] = true; }
  /* Pour toutes les valeurs entre 2 et 1 + la partie     */
  /* entiere de racine de n                               */
    for ( int i = 2 ; i <= (int) (Math.sqrt(n)+1) ; i++ )
  /* si t[i] est vrai -> i est definitivement premier     */
      if ( t[i] )
  /* Construction d'une boucle for pour mettre a faux     */
  /* tous les t[j] ou j est un multiple de i              */
  /* Le for s'initialise a j = 2*i, s'execute tant que    */
  /* j est inferieur ou egal a n, avec un pas egal a i    */
        for ( int j = 2*i ; j <= n ; j = j+i )
  /* t[j] n'est pas premier car multiple d'un nombre      */
  /* premier                                              */
          t[j] = false;
  }

  /* Fonction principale                                  */

  public static void main(String [] args) {
    Console.setTitle("CribleEratosthene");
  /* Lecture au clavier de la valeur pour laquelle        */
  /* on souhaite determiner tous les nombres premiers     */
  /* qui lui sont inferieurs ou egaux                     */
    Console.out.print("Combien de nombres a tester : ");
    int n = Integer.valueOf(Console.in.readLine()).intValue();
  /* Creation d'un tableau de n+1 booleens                */
    boolean [] t = new boolean[n+1];
  /* Realisation du crible d'eratosthene                  */
    cribleEratosthene(n,t);
  /* Affichage du resultat du crible d'eratosthene        */
    afficheTableau(t);
  }
}