C語言與 C++ 尋找 100~200 質數：兩種演算法對比 (試除法優化 vs 埃氏篩)

方法一：試除法優化 (原碼有誤)

原碼內層 j <= 0.5*sqrt(i) **錯誤**，應為 j <= sqrt(i)。0.5*sqrt 會漏判合數 (如 121=11*11, sqrt=11, 0.5*sqrt=5.5, j 只跑到 5，漏掉 11)，導致輸出 119, 121, 143 等合數。

正確試除法 (C/C++ 通用)

#include 
#include 
int main() {
    int count = 0;
    for (int i = 101; i <= 199; i += 2) {
        int limit = (int)sqrt(i);
        int is_prime = 1;
        for (int j = 3; j <= limit; j += 2)
            if (i % j == 0) { is_prime = 0; break; }
        if (is_prime) { printf("%d ", i); count++; }
    }
    printf("\ncount=%d\n", count); // 21
    return 0;
}

方法二：簡單試除法 (j < i)

for (int i = 100; i <= 200; i++) {
    int tag = 0;
    for (int k = 2; k < i; k++) // 未優化到 sqrt
        if (i % k == 0) { tag = 1; break; }
    if (!tag) printf("%d ", i);
}

• 正確但效率低 (O(n²))，小範圍可接受。
• 輸出正確質數 21 個。

C++ 版本差異

• iostream + cmath + namespace std。
• cout << i << ' '; 替代 printf。
• 演算法邏輯相同。

進階：埃氏篩法 (區間篩)

// 篩選 100~200
const int L=100, R=200;
bool is_p[R-L+1]; fill_n(is_p, R-L+1, true);
for (int p=2; p*p<=R; p++) {
    int start = (L+p-1)/p * p; // 第一個 >=L 的 p 倍數
    for (int x=start; x<=R; x+=p)
        if (x != p) is_p[x-L] = false;
}
for (int i=0; i<=R-L; i++) if (is_p[i]) printf("%d ", L+i);