C語言判斷質數（素數）的高效實現與邊界處理

質數定義與判斷邏輯

質數（Prime）是大於 1 的自然數，除 1 和自身外無其他因數。判斷 n 是否為質數：檢查 2 到 √n 是否有因數，有則為合數，否則為質數。

優化實現代碼

#include <stdio.h>
#include <math.h>
#include <stdbool.h>

bool isPrime(unsigned int n) {
    if (n <= 1) return false;      // 0, 1 非質數
    if (n <= 3) return true;       // 2, 3 是質數
    if (n % 2 == 0 || n % 3 == 0) return false;  // 排除 2, 3 的倍數

    // 6k ± 1 優化：所有質數(>3)形式為 6k±1
    for (unsigned int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    }
    return true;
}

int main() {
    unsigned int n;
    printf("請輸入要判斷的數字: ");
    scanf("%u", &n);
    printf("%s\n", isPrime(n) ? "Prime" : "Not Prime");
    return 0;
}

優化技巧解析

• 早期篩選： 排除 ≤1、2、3、偶數、3 的倍數。
• 6k±1 規律： 大於 3 的質數必鄰近 6 的倍數（因 6k, 6k±2, 6k±3, 6k+4 皆可被 2 或 3 整除），迴圈步長 6，每輪檢查 i 和 i+2。
• 迴圈條件 i*i <= n： 避免 sqrt() 浮點運算與精度問題，整數乘法更快。
• 型別選用 unsigned int： 擴展正數範圍，語義更清晰。

複雜度與適用範圍

對於 64 位整數或批次大量判斷，建議用 Miller-Rabin 概率測試或埃拉托斯特尼篩法預計算。

常見錯誤避坑

• 迴圈上界寫 i < sqrt(n) 而非 i*i <= n，邊界易出錯且效能差。
• 未處理 n <= 1 導致誤判。
• 使用 int 導致負數輸入邏輯混淆。
• 針對大數（> 10⁹）仍用試除法，應改用概率演算法。

1. 上一篇文章： C語言結構體參數傳遞陷阱與正確姿勢完整指南
2. 下一篇文章： 順序堆疊（Sequential Stack）C語言完整實現與操作詳解

關於C

C語言字元圖形：雙實心三角組合成菱形實心圖案（星號圖七）

與空心菱形的差異 本程式列印實心菱形，條件判斷從「等於邊緣」

阿姆斯壯數判斷：三位數版本完整解析

什麼是阿姆斯壯數？ 阿姆斯壯數又稱自戀數，指一個 n 位數，

Beej 網絡編程指南（三）：網絡理論與分層模型

數據封裝：網絡通信的核心過程 數據從應用層向下傳遞，每層添加

C語言基礎模擬：不漲薪、不投資、不消費，軟工幾年買得起 200 萬年增 10% 的房

最悲觀假設：房價 200 萬年增 10%，軟工年薪固定 40