C語言求100-200間素數：試除法優化實現

素數判斷與範圍查找算法

素數（質數）指大於1且除1和自身外無其他因數的自然數。求區間素數常用試除法優化版。

核心判斷邏輯

判斷 m 是否為素數，只需試除至 √m：

bool isPrime(int m) {
    if (m < 2) return false;
    if (m == 2) return true;
    if (m % 2 == 0) return false;
    for (int i = 3; i * i <= m; i += 2)
        if (m % i == 0) return false;
    return true;
}

完整程式：100-200 素數列表

#include 
#include 

int main() {
    int count = 0;
    printf("100-200 間的素數:\n");
    for (int m = 101; m <= 200; m += 2) { // 跳過偶數
        int limit = (int)sqrt(m);
        bool prime = true;
        for (int i = 3; i <= limit; i += 2) {
            if (m % i == 0) { prime = false; break; }
        }
        if (prime) {
            printf("%5d", m);
            if (++count % 10 == 0) printf("\n");
        }
    }
    printf("\n共 %d 個素數\n", count);
    return 0;
}

執行結果

100-200 間的素數:
  101   103   107   109   113   127   131   137   139   149
  151   157   163   167   173   179   181   191   193   197
  199
共 21 個素數

優化技巧總結

1. 跳過偶數：從101開始，步長2
2. 試除上限 √m：大幅減少除法運算
3. 試除步長2：只試奇數因子
4. 預計算 sqrt 避免循環中重複調用

進階：埃拉托斯特尼篩法

若需大範圍（如100萬以內）素數，篩法時間複雜度 O(n log log n) 遠優於試除法 O(n√n)。