C/C++ 素數篩選：100-200 區間質數輸出的兩種演算法對比

C/C++ 素數篩選：100-200 區間質數輸出的兩種演算法對比

質數判定是經典演算法題。本文對比**試除法優化版**與**朴素試除法**，並提供 C/C++ 雙語言實現，深入分析時間複雜度與常見邏輯錯誤。

方法一：優化試除法（僅檢查奇數、至 √n）

// C 版本
#include <stdio.h>
#include <math.h>

int main() {
    int count = 0;
    for (int i = 101; i <= 199; i += 2) {  // 僅遍歷奇數
        bool is_prime = true;
        int limit = (int)sqrt(i);
        for (int j = 3; j <= limit; j += 2) {  // 僅用奇數試除
            if (i % j == 0) {
                is_prime = false;
                break;
            }
        }
        if (is_prime) {
            printf("%d ", i);
            count++;
        }
    }
    printf("\ncount=%d\n", count);  // 21
    return 0;
}

// C++ 版本
#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int count = 0;
    for (int i = 101; i <= 199; i += 2) {
        bool is_prime = true;
        int limit = sqrt(i);
        for (int j = 3; j <= limit; j += 2) {
            if (i % j == 0) { is_prime = false; break; }
        }
        if (is_prime) { cout << i << " "; count++; }
    }
    cout << "\ncount=" << count << endl;
    return 0;
}

方法二：朴素試除法（檢查 2 到 n-1）

#include <stdio.h>

int main() {
    int count = 0;
    for (int i = 100; i <= 200; i++) {
        bool is_prime = true;
        for (int k = 2; k < i; k++) {  // 檢查所有可能因數
            if (i % k == 0) { is_prime = false; break; }
        }
        if (is_prime) {
            printf("%d ", i);
            if (++count % 5 == 0) printf("\n");
        }
    }
    return 0;
}

執行結果對比

關鍵 Bug 深度剖析

**優化版輸出包含 119(7×17)、121(11²)、143(11×13)、161(7×23)、169(13²)、187(11×17) 等合數。**

錯誤原因：內層迴圈條件 `j <= 0.5 * sqrt(i)` **嚴重錯誤**。

• 正確邊界：`j <= sqrt(i)` (即 `j*j <= i`)
• 錯誤邊界：`0.5 * sqrt(i)` 使試除範圍縮小 50%，漏檢大於 √n/2 的因數
• 例：i=121，√121=11，正確檢查至 11；錯誤檢查至 5，漏檢 11，誤判為質數

正確優化試除法實現

bool is_prime(int n) {
    if (n < 2) return false;
    if (n == 2 || n == 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    
    // 6k±1 優化：質數(>3)必為 6k±1 形式
    for (int k = 1; 6*k - 1 <= n / (6*k - 1); k++) {
        int d1 = 6*k - 1;
        int d2 = 6*k + 1;
        if (n % d1 == 0 || n % d2 == 0) return false;
    }
    return true;
}

// 或標準 sqrt 版
bool is_prime_sqrt(int n) {
    if (n < 2) return false;
    if (n % 2 == 0) return n == 2;
    for (int i = 3; i * i <= n; i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}

複雜度分析

埃氏篩法實現 (推薦用於區間質數統計)

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

總結

1. 邊界條件決定正確性：`j <= sqrt(i)` 或 `i*i <= n` 是試除法的生命線，`0.5*sqrt(i)` 會產生大量偽質數。
2. 優化順序：先過濾偶數 → 再用 6k±1 → 大範圍用埃氏篩 → 極大範圍用線性篩。
3. C/C++ 差異僅在 I/O：核心邏輯完全一致，`printf`/`cout`、`scanf`/`cin` 互換即可。