C 語言判斷素數算法優化：從 O(n) 到 O(√n) 的關鍵修正

原始代碼問題分析

圖片中的流程圖顯示判斷素數的邏輯為「甚至只須被 2～n」，這會導致時間複雜度達到 O(n)。對於大數判斷極其低效。

核心修正：試除上限優化至 √n

數學原理：若整數 n 有一個大於 √n 的因子，則必定有一個對應的小於 √n 的因子。因此只需檢查 2 到 √n 之間的整數即可。

修正後的流程圖關鍵節點

• 步驟 5：將「甚至只須被 2～n」修正為「甚至只須被 2～√n」
• 步驟 6：判斷條件改為 i ≤ √n

C 語言實現參考

#include 
#include 

bool isPrime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true; // 2, 3 是素數
    if (n % 2 == 0 || n % 3 == 0) return false; // 排除 2 和 3 的倍數
    
    // 只檢查 6k±1 形式的數，進一步減少 1/3 迭代
    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    }
    return true;
}

複雜度對比

常見錯誤避坑指南

• 整數溢位：i * i <= n 中若 n 接近 INT_MAX，i*i 會溢位，建議改用 i <= n / i 或 (long long)i * i <= n
• 邊界條件：1 不是素數，2 是唯一的偶素數
• 浮點數誤差：避免使用 sqrt(n) 進行循環判斷，整數運算更可靠