import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception{
          long startTime = System.nanoTime();
          Scanner sc = new Scanner(System.in);
          double number = sc.nextDouble();
          double num = Math.pow(number,0.5);
          double N = Math.round(num) + 1;
          if(number % 2 == 0){
               System.out.println(Math.round(number) + "は素数ではありません。");
               System.out.println("少なくとも2を因数に持ちます。");
          }
          for(double i = 3;i <= N;i+=2){
               if(number % i == 0){
                    System.out.println(Math.round(number) + "は素数ではありません。");
                    System.out.println("少なくとも" + Math.round(i) + "を因数に持ちます。");
                    break;
               }
               if(i == N){
                    System.out.println(Math.round(number) + "は素数です。");
               }
               if(i == Math.round(num)){
                    System.out.println(Math.round(number) + "は素数です。");
               }
          }
          long endTime = System.nanoTime();
          long Time = endTime - startTime;
          System.out.println("処理時間:" + (double)Time / 1000000000 + "秒");
     }
}