C 語言判斷質數（素數）的最佳實踐：根號優化與邊界處理

核心邏輯

質數定義：大於 1 的自然數，除 1 與自身外無其他因數。檢查範圍只需到 √n，因若 n = a×b 則至少一因子 ≤ √n。

標準實作

#include 
#include 

int is_prime(unsigned int n) {
    if (n <= 1) return 0;           // 1 不是質數
    if (n == 2) return 1;           // 2 是唯一偶質數
    if (n % 2 == 0) return 0;       // 排除其他偶數
    for (unsigned int i = 3; i <= sqrt(n); i += 2) // 只檢查奇數
        if (n % i == 0) return 0;
    return 1;
}

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

關鍵優化點

1. 提早返回：n<=1、n==2、偶數直接判定
2. 迴圈步進 2：跳過偶數，減半迭代次數
3. 邊界 i <= sqrt(n)：含等號確保完全平方數（如 9, 25）能被檢測
4. 型別用 unsigned int：避免負數干擾，擴大範圍

進階：Miller-Rabin 確定性版本（64-bit 範圍）

對於 uint64_t，可用基底 {2, 3, 5, 7, 11, 13} 的 Miller-Rabin 確定性測試，O(k log³n) 速度極快，適合大整數場景。