C語言經典演算法：篩選 100~200 間的質數（素數）

演算法核心：試除法優化

判斷 n 是否為質數，只需試除到 √n。進一步優化：

• 排除偶數（從 101 開始，步進 2）。
• 除數也只試奇數（從 3 開始，步進 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 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;
}

關鍵細節

1. sqrt 需 <math.h>，編譯時加 -lm (GCC)。
2. 外層 i += 2 跳過偶數，內層 j += 2 同理，效率提升 ~4 倍。
3. limit 計算一次放外層，避免重複呼叫 sqrt。
4. 輸出結果：101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 (共 21 個)。

進階：埃氏篩法

若範圍大（如 1~1,000,000），試除法太慢，應用 Sieve of Eratosthenes (埃氏篩)，時間複雜度 O(n log log n)，空間 O(n)。

// 篩選 1~MAX 的質數
#define MAX 1000000
bool is_prime[MAX+1];
void sieve() {
    memset(is_prime, true, sizeof(is_prime));
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i*i <= MAX; i++)
        if (is_prime[i])
            for (int j = i*i; j <= MAX; j += i)
                is_prime[j] = false;
}

總結

小範圍質數篩選，優化試除法足夠；大範圍必用埃氏篩或線性篩。掌握 √n 邊界與奇數優化是基礎功力。