/**
 * legge da input standard un numero intero positivo
 * e segnala su output standard se il numero e' primo.
 * Il programma termina quando viene letto da input standard
 * il carattere sentinella 'Q'
 *
 * @author Adriano Luchetta
 * @version 18-Ott-2003
 * @version 28-Ott-2004
 */

/* 
   per verificare se un numero intero positivo n e' primo si divida
   n per i numeri interi dell'insieme J = {j| j >= 2 && j*j <= n}.
   L'algoritmo non e' efficiente.
   L'algoritmo del Crivello di Eratostene e' piu'
   efficiente, ma non sappiamo ancora programmarlo.
*/

import java.util.Scanner;

public class RiconoscitoreNumeriPrimi
{
   public static void main(String[] args)
   {
      final String SENTINELLA = "Q";

      Scanner in = new Scanner(System.in);

     System.out.println("*******************************************");
     System.out.println("*** Programma che verifica se il numero ***");
     System.out.println("*** intero positivo n e' primo          ***");
     System.out.println("*******************************************");

     while (true)    // questo ciclo termina quando viene acquisito
     {               // il carattere sentinella
        System.out.print("n?: ");

        String line = in.next();
        if (line.equalsIgnoreCase(SENTINELLA))
        {
           System.out.println("***Fine Programma***");
           return;    // termina il metodo main
        }

        int n = Integer.parseInt(line);

        if (n <= 0)
           System.out.println(n + ": ingresso non ammesso");
        else
        {
           int j = 2;
           boolean primo = true;
           while (primo && ((j * j) <= n))
           {
              primo = (n % j) != 0;  // se esiste un divisore il numero non e' primo
              j++;
           }

           if (primo)
              System.out.println(n + " e' primo"); // si noti che funziona anche per j = 1, 2, 3
           else
              System.out.println(n + " e' divisibile per " + (j-1));
        }
     }
  }
}