/* verifica se un naturale in input e' primo 
 * versione efficiente
 */

import java.util.Scanner;

public class PrimalitaEfficiente {
	public static void main(String[] args) {
		long n, divisore;
		long maxDiv;
		boolean trovatoDivisore;
		Scanner lett = new Scanner(System.in);
		
		System.out.print("Digita un intero positivo: ");
		n = lett.nextLong();
		
/* se esistono divisori allora almeno uno e' <= della radice di n
 * Il metodo sqrt restituisce un double, e la conversione a long
 * potrebbe introdurre troncamenti
 * E' quindi opportuno aggiungere 1 a maxDiv
 */
		maxDiv = (long) Math.sqrt(n) + 1;
		divisore = 2;
		trovatoDivisore = false;
		while(divisore <= maxDiv) {
			if((n%divisore) == 0) {
				trovatoDivisore = true;
			}
			divisore++;
		}
		if(trovatoDivisore)
			System.out.println("Il numero " + n + " e' composto.");
		else
			System.out.println("Il numero " + n + " e' primo.");
	}
}