C語言判斷素數函數：從錯誤代碼到標準實現的遞進優化

原始錯誤代碼分析

int s(int m) {
    int i;
    for (i = 0; i < m/2; i++) {  // ❌ i=0 導致 m%0 除零崩潰
        if (m % i == 0) return 0; // ❌ 邏輯反：能整除說明非素數，應返回 0
        else return 1;            // ❌ 迴圈第一輪就返回，無法檢查完所有因子
    }
}

標準正確實現

// 返回 1=素數，0=非素數
int is_prime(int n) {
    if (n <= 1) return 0;           // 1 及以下非素數
    if (n <= 3) return 1;           // 2, 3 是素數
    if (n % 2 == 0 || n % 3 == 0) return 0; // 排除 2、3 的倍數

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

演進對比：四種寫法

完整可測試程序

#include 
#include 

bool is_prime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (int i = 5; i * i <= n; i += 6)
        if (n % i == 0 || n % (i + 2) == 0) return false;
    return true;
}

int main() {
    int n;
    printf("輸入整數: ");
    scanf("%d", &n);
    printf("%d %s素數\n", n, is_prime(n) ? "是" : "不是");
    // 批量測試
    printf("\n100 以內素數: ");
    for (int i = 2; i <= 100; i++)
        if (is_prime(i)) printf("%d ", i);
    puts("");
    return 0;
}

常見錯誤避坑

1. ❌ for(i=0; ...) → 除零崩潰。起始必須 ≥ 2。
2. ❌ if (n%i==0) return 1; else return 0; → 邏輯反、且首輪即返回。**能整除=非素數=返回 0/false**。
3. ❌ i <= n/2 → 邊界過大，性能差。**i*i <= n 等價且更快**（避免除法/浮點）。
4. ❌ 忽略 n <= 1 → 1、0、負數誤判為素數。

擴展：篩法求區間素數（埃拉托斯特尼篩）

void sieve(int limit) {
    bool *is_p = calloc(limit + 1, sizeof(bool));
    for (int i = 2; i <= limit; i++) is_p[i] = true;
    for (int i = 2; i * i <= limit; i++)
        if (is_p[i])
            for (int j = i * i; j <= limit; j += i)
                is_p[j] = false;
    for (int i = 2; i <= limit; i++)
        if (is_p[i]) printf("%d ", i);
    free(is_p);
}

適合**批量查詢**、靜態上限已知場景，時間 O(n log log n)。

總結

• **素數判斷核心**：遍歷潛在因子，發現能整除即返回非素數。
• **最佳常規寫法**：6k±1 優化 + i*i <= n 邊界 + 邊界情況預處理（≤3、偶數、3的倍數）。
• **批量場景用篩法**，單次查詢用試除法。
• 函數返回 bool（需 stdbool.h）語義比 int 0/1 更清晰。