C語言經典例題：判斷並輸出 101-200 間所有素數

素數判定優化原理

若 n 有因數，必有一因子 ≤ √n。故只需試除 2 到 ⌊√n⌋。

完整代碼

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

int main() {
    int count = 0;
    for (int m = 101; m <= 200; m++) {
        int limit = (int)sqrt(m);
        int is_prime = 1;
        for (int i = 2; i <= limit; i++) {
            if (m % i == 0) { is_prime = 0; break; }
        }
        if (is_prime) {
            printf("%-4d", m);
            if (++count % 10 == 0) printf("\n");
        }
    }
    printf("\n總共有 %d 個素數\n", count);
    system("pause");
    return 0;
}

輸出結果

101  103  107  109  113  127  131  137  139  149
151  157  163  167  173  179  181  191  193  197
199
總共有 21 個素數

進階優化

• 預先篩選偶數：if (m%2==0) continue; 後只試奇數除數。
• 埃拉托斯特尼篩法（Sieve of Eratosthenes）適用於大範圍批量求素數。