/**
 * @作者: 劉先章
 * @學號: n936725
 * @題目: 1.輸入一整數,判斷是否為質數
 *
 */

/**
 * 質數的定義:除了1及本身之外,沒有任何其它的因數
 * 尋找方法:(假設;欲判斷的質數為p)
 * 一、初階方法:直接從2到(p-1)逐一測試,如果p能整除該值即表示,p不為質數,反之則為質數
 * 二、進階方法:考慮如何減少測試的範圍,可能做法有二
 *           1.縮小測試的最大值:假設;p不為質數,p值必存在二個因數n1*n2(n1,n2均大於1),因此只要找到n1或是n2
 *                      為p的因數時,即可証明p不為質數。
 *                      如果n1>n2,則在找尋過程中,因數n2必然會先被找到,反之n1<n2時,因數n1會先被找到,
 *                      因此,我們只要尋找到當n1=n2時的值,即可找到是否有因數的所有可能性
 *                      p=n1*n2,當n1=n2時,p=n1^2(^表示平方),即n1=sqrt(n1)(sqrt為開平方根)
 *                      結論就是,我們只要尋找2...sqrt(p)的範圍,如果在範圍內沒有任何p的因數,即可以
 *                      証明p為質數!(如果去找大於n1的值,表示n2早已經被找過了,反之亦然,因此 這麼作是沒有必要的)
 *          2.減少測試值:在2...sqrt(p)之間,只要用這個範圍內的質值去測試p即可,因為在這範圍內的非質數,都可以
 *                   找到其因數,而這些因數一定可以分解到最小的質數,因此去用非質數來除p,顯然是多餘的(可被
 *                   非質數整除,就一定能被比它小的質數整除)
 *                   例子:要判斷63是否為質數,一開始會由3來測試,因為3是63的因數,因此就沒有必要再去測試6,
 *                      9,12,15,18...這些值
 *                   結論就是,如果要找一數是否為質數(例如63),我們只要找2,3,5,7這些數是否能被63整除,如果
 *                   都不行,那63就是質數! (63的平方根取整數為7)
 *             困難點:我們無法預先得知2...sqrt(p)中間的質數有那些,所以只能退而求其次,只略過所有2的倍數值(因
 *                 為2的 倍數,數量最多),所以其要測試的數值為:2,3,5,7,9,11...sqrt(p)
 *                 另外,由於sqrt(p)可能為一實數,因此我們會取(int或long)sqrt(p)+1來做為最大測試值
 */
import java.io.*;
public class quiz1 {

   public static void main(String[] args) throws IOException
   {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      System.out.println("請輸入大於2的整數:");
      String str = br.readLine();
      long prime = Long.parseLong(str);
      if (prime < 2)
      {
         System.out.println("您所輸入的數字必須大於2!");
      }
      else
      {
         long i = 2;               // 設定i為測試者,從2開始測試
      //   long maxPrime = (long)Math.sqrt(prime) + 1;   // 設定需測試的最大值,見前面的解說
                                          
         long maxPrime = prime / 2 + 1;              /* 由於Math.sqrt()超出目前課本範圍,
                                                                         * 故用prime/2+1來縮小需測試的範圍
                                                                         * 這裡不再証明:
                                                                         * 如果prime>=2
                                                                         * 則(long)sqrt(prime)+1 <= (long)(prime/2)+1   
                                                                         */
         boolean isPrime = true;      // 設定一個布林值,用來記錄是否測試到不為質數的值
         while (i <= maxPrime)       // 測試範圍為2...maxPrime
         {
            if (prime % i == 0)
            {
               isPrime = false;   // 如果prime能被i整除,表示prime不為質數,因此isPrime就設為false
               break;              // 並結束測試
            }
            i += (i == 2)?1:2;      // 步進值為2,3,5,7...,原因請見 前面的解釋
         }
         if (isPrime)
            System.out.println(prime+"是質數!");
         else
            System.out.println(prime+"不是質數,它至少有一個因數為"+i);
      }
   }
}