C 語言印出 1~200 間所有質數：試除法與優化技巧

質數定義

大於 1 的自然數，除 1 與自身外無其他正因數。1 **不是**質數。

試除法核心邏輯

判斷 m 是否為質數：只需檢查 2 ~ sqrt(m) 是否有因數。若無，則為質數。

完整實現（每行 10 個，統計總數）

#include 
#include 

int main() {
    int count = 0;
    for (int m = 2; m <= 200; m++) {  // 從 2 開始，1 非質數
        int limit = (int)sqrt(m) + 1; // +1 確保涵蓋完全平方數
        bool is_prime = true;
        for (int i = 2; i <= limit; i++) {
            if (m % i == 0) { is_prime = false; break; }
        }
        if (is_prime) {
            printf("%-4d", m);
            if (++count % 10 == 0) putchar('\n');
        }
    }
    printf("\nTotal primes: %d\n", count);  // 輸出 46
    return 0;
}

關鍵優化細節

1. 外層從 2 開始：1 非質數，避免誤判。
2. 內層上限 sqrt(m)：若 m = a*b，則 a ≤ sqrt(m) 或 b ≤ sqrt(m)，故只需檢查至平方根。
3. +1 修正：(int)sqrt(9) = 3，需檢查 3；+1 確保 i=3 被檢查。
4. 早期中斷：發現因數立即 break，避免無謂迴圈。
5. 格式化輸出：%-4d 左對齊寬度 4，每 10 個換行。

進階優化：埃拉托斯特尼篩法

若需求範圍大（如 1~1,000,000），試除法 O(n√n) 過慢。篩法 O(n log log n) 更優：

void sieve(int n) {
    bool *is_prime = calloc(n + 1, sizeof(bool));
    for (int i = 2; i <= n; i++) is_prime[i] = true;
    for (int i = 2; i * i <= n; i++)
        if (is_prime[i])
            for (int j = i * i; j <= n; j += i)
                is_prime[j] = false;
    for (int i = 2; i <= n; i++)
        if (is_prime[i]) printf("%d ", i);
    free(is_prime);
}

總結

1~200 質數共有 **46 個**。試除法配合 sqrt 上限與早期中斷，足以應對中小範圍質數列印；大範圍請改用篩法。