/*
 * 以篩法檢驗輸入之正整數是否質數
 * skj  3/28/2011
 * 
 * 虛擬碼
 * 
 * 1. 令輸入之正整數為x
 * 3. if x 等於 1
 *    {
 * 3.1  isPrime = false
 *    }
 *    else if x 等於 2
 *    {
 * 3.2  isPrime = true
 *    }
 *    else if x 被 2 整除
 *    {
 * 3.3  isPrime = false
 *    }
 *    else
 *    {
 * 3.4  令小於x之平方根為yMax
 * 3.5  isPrime = true
 * 3,6  for(y=3; y<=yMax; y += 2)
 *      {
 * 3.6.1  if x 不被 y 整除  continue
 * 3.6.2  isPrime = false
 * 3.6.3  break
 *      }
 *    }
 * 4. 根據 isPrime 決定 x 是否質數
 * 
 * 
 * 測試規劃:
 *
 * 測試虛擬碼步驟3.1
 * 1 不是質數 
 * 
 * 測試虛擬碼步驟3.2
 * 2 是質數
 * 
 * 測試虛擬碼步驟3.3
 * 4 不是質數  
 * 32 不是質數
 *  
 * 測試虛擬碼步驟3.4~3.6
 * 3 是質數 (for迴圈不執行)
 * 5 是質數 (for迴圈不執行)
 * 9 不是質數 (迴圈變數y = 3; 平方數, 檢驗是否有邊界錯誤)
 * 11 是質數  (迴圈變數y = 3)
 * 15 不是質數  (迴圈變數y = 3)
 * 25 不是質數 (迴圈變數y = 3, 5; 平方數, 檢驗是否有邊界錯誤)
 * 29 是質數  (迴圈變數y = 3, 5)
 * 35 不是質數 (迴圈變數y = 3, 5)
 * 49 不是質數 (迴圈變數y = 3, 5, 7; 平方數, 檢驗是否有邊界錯誤)
 * 53 是質數 (迴圈變數y = 3, 5, 7)
 * 91 不是質數 (迴圈變數y = 3, 5, 7)
 */



using System;

namespace PrimeNumberChecking
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.Write("輸入正整數x:");
            int x = int.Parse(Console.ReadLine());
            bool isPrime = true;
            if (x == 1)
            {
                isPrime = false;
            }
            else if (x == 2)
            {
                isPrime = true;
            }
            else if (x % 2 == 0)
            {
                isPrime = false;
            }
            else
            {
                int yMax = (int)Math.Sqrt(x);
                for (int y = 3; y <= yMax; y += 2)
                {
                    if (x % y != 0) continue;
                    isPrime = false;
                    break;
                }
            }
            string result = isPrime ? "是質數" : "不是質數";
            Console.WriteLine("{0}"+result, x);
        }
    }
}