要快速判斷一個數是否為質數，可以采用以下優化后的試除法，結合數學規律大幅減少計算量：

步驟說明

1. 處理特殊情況：

   • 若 ( n \leq 1 )，不是質數。
   • 若 ( n = 2 ) 或 ( n = 3 )，是質數。
   • 若 ( n ) 能被 2 或 3 整除，不是質數。

2. 優化試除范圍：

   • 所有質數（除 2 和 3）都可表示為 ( 6k \pm 1 ) 的形式。
   • 只需檢查 ( 5 ) 到 ( \sqrt{n} ) 之間的 ( 6k \pm 1 ) 的數。

3. 循環檢查：

   • 以 6 為步長，每次檢查 ( i ) 和 ( i+2 ) 是否能整除 ( n )。

C++ 代碼實現

#include <iostream>
#include <cmath>using namespace std;bool is_prime(int n) {if (n <= 1) return false;       // 小于等于1的數不是質數if (n <= 3) return true;        // 2和3是質數if (n % 2 == 0 || n % 3 == 0)  // 排除能被2或3整除的數return false;// 檢查形如6k±1的數，直到i超過sqrt(n)for (int i = 5; i * i <= n; i += 6) {if (n % i == 0 || n % (i + 2) == 0)return false;}return true;
}int main() {int num;cout << "輸入一個整數: ";cin >> num;if (is_prime(num))cout << num << " 是質數" << endl;elsecout << num << " 不是質數" << endl;return 0;
}

復雜度分析

• 時間復雜度：( O(\sqrt{n}) )，但實際運行次數比普通試除法減少約 3 倍。
• 空間復雜度：( O(1) )，僅需常數空間。

優化原理

1. 減少除數范圍：通過數學推導，質數必定出現在 ( 6k \pm 1 ) 的序列中，避免檢查不必要的數。
2. 提前終止條件：當 ( i^2 > n ) 時停止循環，確保只檢查到 ( \sqrt{n} )。
3. 快速排除偶數：先處理 2 和 3 的倍數，直接跳過后續循環。

示例測試

• 輸入：7 → 輸出：是質數
• 輸入：25 → 輸出：不是質數（5×5）
• 輸入：997 → 輸出：是質數（大質數）
• 輸入：1000001 → 輸出：不是質數（101×9901）

這種方法結合數學規律和代碼優化，能高效處理大多數情況下的質數判斷需求。對于極大數（如加密用的大質數），可進一步使用概率性算法如 米勒-拉賓素性測試 進行更快速判斷。