/**
 * CalcolatoreNumericoEratostene
 *   calcolatore numerico - aggiornamento
 *
 *   @author Adriano Luchetta
 *
 *   @version 21-Ott-2005
 *   @version 6-Nov-2004
 *   @version 25-Ott-2003
 */
import java.util.Scanner;
public class CalcolatoreNumericoEratostene
{
   /**
      verifica se un numero intero positivo n e' primo, usando l'algoritmo
      detto "Crivello di Eratostene".
      @param n il numero su cui viene effettuata la verifica
      @return true se il numero e' primo, false altrimenti.
   */
   public static boolean primo(int n)
   {
     boolean[] isDivided = new boolean[n + 1];

     int i = 2;
     while (!isDivided[n] && i * i <= n)
     {
        for (int j = i + i; j <= n; j += i)
          isDivided[j] = true;

        do
          i++;
        while (isDivided[i]);
     }
     return !isDivided[n];
   }

   /**
   metodo main() di prova
   */
   public static void main(String[] args)
   {
      Scanner reader = new Scanner(System.in);

      System.out.print("Inserire un numero intero positivo: ");
      int n = Integer.parseInt(reader.nextLine());
      
      if (primo(n))
         System.out.println(n + " e' primo");
      else
         System.out.println(n + " non e' primo");
   }
}