C 語言求素數三種寫法：雙循環、優化至 √n、布爾標記法

需求

輸出 100~200 之間所有素數。

方法一：雙層循環（教學基礎版）

for (int i = 100; i <= 200; ++i) {
    int j;
    for (j = 2; j <= i-1; ++j)
        if (i % j == 0) break;
    if (j == i) printf("%d ", i);
}

方法二：優化至 √n + 跳過偶數

for (int i = 101; i <= 200; i += 2) { // 只檢查奇數
    int j;
    for (j = 2; j * j <= i; ++j) // 只試除到 √i
        if (i % j == 0) break;
    if (j * j > i) printf("%d ", i);
}

方法三：布爾標記法（可讀性佳）

#include <stdbool.h>
for (int i = 100; i <= 200; ++i) {
    bool isPrime = true;
    for (int j = 2; j * j <= i; ++j)
        if (i % j == 0) { isPrime = false; break; }
    if (isPrime) printf("%d ", i);
}

進階：埃氏篩

若需大範圍（如 1~10^6）求素數，用 埃拉托斯特尼篩法 O(n log log n) 批量篩選，比逐個試除快得多。

總結

• 教學理解用方法一；
• 工程/競賽用方法二或埃氏篩；
• 方法三代碼最清晰，推薦日常使用。