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

import java.io.*;

public class CribleEratosthene {
  static BufferedReader flux = new BufferedReader(new InputStreamReader(System.in));

  /* Fonction d'affichage de tous les booleens contenus   */
  /* dans un tableau de booleens                         */

  public static void affichage(boolean [] t) {
    int i;
  /* Pour toutes les valeurs d'indice 0 a t.length-1 inclus    */
    for ( i = 0 ; i < t.length ; i++ )
      System.out.println(t[i]);
  }

  /* Fonction d'affichage de tous les entiers codes comme */
  /* premiers (true) dans un tableau de booleens          */

  public static void affichageNombresPremiers(boolean [] t) {
    int i;
  /* Pour toutes les valeurs d'indice 0 a t.length-1 inclus    */
    for ( i = 0 ; i < t.length ; i++ )
      if ( t[i] )
        System.out.println(i+1);
  }

  /* Fonction d'initialisation a true des booleens       */
  /* contenus dans un tableau de booleens                */
  /* sauf la premier a false                             */

  public static void initialisationTableau(boolean [] t) {
    int i;
    t[0] = false;
  /* Pour toutes les valeurs d'indice 1 a t.length-1 inclus    */
    for ( i = 1 ; i < t.length ; i++ ) {
      t[i] = true; }
  }

  /* Fonction de calcul d'un tableau de booleens         */
  /* codant les nombres premiers (true pour premier,     */
  /* false pour non premier)                             */

  public static boolean [] realiseCribreEratosthenet(int n) {
  /* Declaration et allocation d'un tableau de n booleens      */
    boolean [] tab = new boolean[n];
  /* Initialisation du tableau tab                             */
    initialisationTableau(tab);
  /* Calcul de la valeur limite de criblage                    */
    int limite =(int) Math.sqrt(n);
  /* Pour tous les entiers de 2 a limite                       */
    for ( int i = 2 ; i <= limite ; i++ )
  /* Si i est un nombre premier                                */
      if ( tab[i-1] )
  /* Tous les multiples de i entre 2*i et n inclus ne sont pas */
  /* des nombres premiers                                      */
        for ( int j = 2*i ; j <= n ; j += i )
          tab[j-1] = false;
    return(tab);
  }

  /* Fonction principale                                  */
  
  public static void main(String [] args) throws IOException {
    int nb;
    boolean [] tableau;
  /* Lecture clavier du nombre jusqu'ou realiser le criblage   */
    System.out.println("Valeur limite jusqu'ou rechercher:");
    nb = Integer.valueOf(flux.readLine()).intValue();
  /* Realisation du crible                                     */
    tableau = realiseCribreEratosthenet(nb);
    System.out.println();
    System.out.println("Tableau de booleens obtenu");
  /* Affichage du tableau de booleens brut                     */
    affichage(tableau);
    System.out.println();
    System.out.println("Nombres premiers entre 2 et "+nb);
  /* Affichage des nombres premiers codes dans un tableau      */
  /* de booleens                                               */
    affichageNombresPremiers(tableau);
  }
}