17.4 根號複雜度：質數判斷

本站題目〈質數判斷〉：Q \le 100 筆詢問，每筆給一個不超過 10^{11} 的正整數，判斷是不是質數。

上冊 4.5 的做法是拿 2 到 n-1 逐一試除——O(n)。這裡 n 到 10^{11}，單筆詢問就要一百秒，連一筆都跑不完。

換形狀的鑰匙在 10.1 就鋪過：因數成對出現。36 = 2 \times 18 = 3 \times 12 = 4 \times 9 = 6 \times 6，每一對裡總有一個不超過 \sqrt{36} = 6——所以試到 \sqrt{n} 都沒找到因數，就能斷定 n 是質數。試除範圍從 n 砍到 \sqrt{n}，10^{11} 變成約 3.2 \times 10^5。

還有兩個實戰細節：

• 多筆詢問，包成函式。同一件事要做 Q 次，寫成 isPrime(n) 一支函式（上冊第七單元），主程式一行一筆，乾淨又不易錯。
• 判斷「試到 \sqrt{n}」不要用浮點數的 sqrt。9.8 說過大整數轉浮點會失真；改用 d * d <= n 這個純整數條件，完全避開浮點——但注意 d 要宣告成 long long：d 可到 3.2 \times 10^5，d \times d 約 10^{11}，int 裝不下。

¶完整程式碼

#include <iostream>
using namespace std;

bool isPrime(long long n) {
    if (n < 2) return false;
    for (long long d = 2; d * d <= n; d++) {   // 只試到 sqrt(n)：因數成對
        if (n % d == 0) return false;
    }
    return true;
}

int main() {
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        long long n;
        cin >> n;
        cout << (isPrime(n) ? 1 : 0) << '\n';
    }
    return 0;
}

執行結果（輸入 6 與 7、6、1、2、99、97）：

1
0
0
1
0
1

估一下總量：每筆最多約 3.2 \times 10^5 次試除、100 筆共約 3 \times 10^7 次——10.1 三步驟一套，穩穩過關。O(n) 到 O(\sqrt{n}) 這一階，是「換形狀」收益最誇張的一階之一：n 越大，\sqrt{n} 相對越小。