C語言求 100~200 間的質數：優化版試除法

問題描述

列印 100 到 200 之間的所有質數（素數），並統計個數。

優化策略

• 偶數直接跳過：從 101 開始，步進 2 (i += 2)。
• 試除上限只需到 sqrt(i)：若無因數則為質數。
• 試除因數亦跳過偶數：j += 2。

完整程式碼

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

int main() {
    int count = 0;
    for (int i = 101; i <= 199; i += 2) {        // 只檢查奇數
        int limit = (int)sqrt(i);
        int j;
        for (j = 3; j <= limit; j += 2) {        // 只用奇數試除
            if (i % j == 0) break;
        }
        if (j > limit) {                           // 沒找到因數
            printf("%d ", i);
            count++;
        }
    }
    printf("\ncount=%d\n", count);
    return 0;
}

輸出結果

101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199
count=21

複雜度分析

• 外層迴圈約 50 次 (奇數個數)。
• 內層迴圈最多 sqrt(199)/2 ≈ 7 次。
• 總操作數極小，瞬間完成。

進階優化方向

• 預先建立小質數表 (埃拉托斯特尼篩法) 供試除使用。
• 米勒-拉賓素性測試 (適用大整數)。
• 位元組篩 (Bitwise Sieve) 節省記憶體。