C 語言素數判斷：單個整數素性測試的試除法優化與邊界處理

問題描述

輸入一個大於 1 的整數，判斷是否為素數。核心考點：試除法邊界優化、特殊情況處理 (2, 偶數)、標誌變量用法。

原代碼分析

#include <stdio.h>

int main() {
    int i, num, flag = 1;
    printf("請輸入大於1的整數: ");
    scanf("%d", &num);

    if (num == 2) flag = 1;
    else {
        for (i = 2; i <= num/2; i++) {  // ❌ 優化至 √num
            if (num % i == 0) { flag = 0; break; }
        }
    }

    if (flag) printf("%d 是素數\n", num);
    else printf("%d 不是素數\n", num);
    return 0;
}

優化版：√n 邊界 + 偶數快速排除

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) return false;  // 排除 2,3 的倍數

    // 6k±1 模式試除
    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}

關鍵優化點對比

邊界測試用例

大數擴展：64 位整數與米勒-拉賓

對於 64 位整數 (≤ 2⁶⁴)，確定性米勒-拉賓測試僅需測試基數 {2, 3, 5, 7, 11, 13, 17} 即可 100% 正確，極快。

// 64位確定性米勒-拉賓 (簡化框架)
bool miller_rabin_64(uint64_t n) {
    if (n < 2) return false;
    // 小素數快速檢查
    for (uint64_t p : {2,3,5,7,11,13,17,19,23,29,31,37})
        if (n % p == 0) return n == p;
    // 寫入 n-1 = d * 2^s
    // 對基數 a ∈ {2, 325, 9375, 28178, 450775, 9780504, 1795265022} 測試
    // ...
}

總結

素數判斷是試除法優化的縮影。關鍵收穫：

• 試除上界 √n 由數學定理保證；
• 6k±1 模式 為 32/64 位整數工程標準試除法；
• 特殊值 (1, 2, 3, 偶數) 必須前置處理；
• 大數 (64位) 必用 米勒-拉賓，試除法不可行；
• 函數封裝 bool is_prime(int) 利於復用與測試。