C語言實現100-200間素數篩選優化算法

C語言求100至200間素數：從定義到優化實現

素數判定是經典程式設計練習。本文展示如何從基本定義出發，逐步優化至平方根判定法，並給出完整 C 語言實現代碼。

素數判定邏輯演進

基本定義法

素數只能被 1 和自身整除。最直觀方法：對每個數 n，檢查 2 到 n-1 是否有因數。時間複雜度 O(n²)，效率極低。

優化策略

1. 跳過偶數：除 2 外無偶數素數，步長設為 2
2. 平方根截斷：若 n 為合數，最小質因數 ≤ √n，只需檢查到 √n

優化後算法實現

#include <stdio.h>
#include <math.h>

int main() {
    int count = 0;
    for (int m = 101; m <= 200; m += 2) {  // 只檢查奇數
        int limit = (int)sqrt(m);
        int i;
        for (i = 2; i <= limit; i++) {
            if (m % i == 0) break;  // 發現因數，非素數
        }
        if (i > limit) {  // 循環正常結束，無因數
            printf("%d ", m);
            count++;
        }
    }
    printf("\ncount=%d\n", count);
    return 0;
}

關鍵控制流說明

• break：跳出內層循環，直接進入素數判定邏輯
• continue：本例未使用，但可用於跳過特定條件繼續下一輪
• 外層循環步長 2 減少一半迭代次數

執行結果分析

程式輸出 100-200 間所有素數及總數，驗證算法正確性。此優化將判定複雜度從 O(n) 降至 O(√n)，配合奇數篩選，效率顯著提升。

擴展思考

更大範圍素數篩選可採用埃拉托斯特尼篩法，空間換時間實現 O(n log log n) 複雜度，適合批量素數生成場景。