07｜質數判斷

還沒完成C 或 C++ 皆可CPU 時間上限 1 秒

相關主題： C 基礎速查、資料型態與範圍

題目說明

C 或 C++ 皆可｜CPU 時間上限 1 秒

題目

質數是大於 1、而且除了 1 和它自己以外，沒有其他正因數的整數，例如 2、3、5、7、11。1 不是質數。

給你 T 個正整數，判斷每一個是不是質數。

請把判斷寫成一個函式 is_prime：傳入一個整數，回傳它是不是質數（C 和 C++ 都回傳 bool）。main 只負責輸入和輸出。

注意：數字最大有 10 億，從 2 一路試到 n - 1 的寫法會超過時間。

輸入

第一行是一個整數 T（1 ≤ T ≤ 10,000），代表有幾個數字。

接下來 T 行，每行一個整數 n（1 ≤ n ≤ 1,000,000,000）。

輸出

輸出 T 行，依照輸入的順序，n 是質數就輸出 yes，不是就輸出 no。

範例

輸入：

輸出：

no
yes
yes
no
yes
no
yes
no

複習重點

函式：回傳型別、參數、return。return 會立刻結束函式，找到答案就可以提早回傳
C：要用 bool 需要 #include <stdbool.h>；C++ 的 bool 是內建型別
函式要寫在 main 的前面，或是先在前面宣告（只寫函式的第一行，加分號）
如果 n = a × b 而且 a ≤ b，那 a × a ≤ n，所以只要試到 √n 就夠了
迴圈條件 i * i <= n 的溢位陷阱：i 是 int 時，如果 n 接近 int 的上限（約 21 億），i * i 可能超出 int 的範圍

提示 1：為什麼只要試到 √n？

如果 n 不是質數，就可以寫成 n = a × b，其中 2 ≤ a ≤ b。這時 a × a ≤ a × b = n，所以 a ≤ √n。

也就是說：如果 n 有因數，一定有一個因數 ≤ √n。從 2 試到 √n 都沒有整除，n 就是質數。

10 億的 √ 大約是 31623，每個數字最多試 3 萬多次，而不是 10 億次。

提示 2：迴圈條件怎麼寫比較好？

不建議用 i <= sqrt(n)：sqrt 用的是浮點數，可能有誤差，而且每一圈都重新計算。用整數來寫：

i * i <= n：簡單直接，但要注意 i * i 會不會溢位。這一題 n 最大 10 億，int 的 i * i 剛好不會溢位；如果 n 可以到 int 的上限就會出事，可以把 i 宣告成 long long
i <= n / i：意思一樣，但完全不會溢位

提示 3：函式的樣子

bool is_prime(int n) {
    if (n < 2) {
        return false;
    }
    for (int i = 2; /* 條件？ */; i++) {
        // 如果 i 整除 n，n 就不是質數
    }
    return true;
}