三種循環實現 1-100 質數篩選（while / do-while / for）

演算法核心：試除法判斷質數

對整數 m (2 ≤ m ≤ 100)，檢查是否存在除數 d (2 ≤ d ≤ √m)。無除數則為質數。

優化：d 只需檢查到 √m（或 m/2 粗略上界），甚至可先排除偶數。

版本一：while 迴圈

#include 
void main() {
    int i = 2, j, n, m;
    while (i < 101) {
        m = 1; n = i / 2; j = 2;
        while (j <= n) {
            if (i % j == 0) { m = 0; break; }
            j++;
        }
        if (m) cout << i << " ";
        i++;
    }
}

版本二：do-while 迴圈

#include 
void main() {
    int i = 2, j, n, m;
    do {
        m = 1; n = i / 2; j = 2;
        do {
            if (i % j == 0) { m = 0; break; }
            j++;
        } while (j <= n);
        if (m) cout << i << " ";
        i++;
    } while (i < 101);
}

版本三：for 迴圈（最簡潔）

#include 
void main() {
    int i, j, n, m;
    for (i = 2; i < 101; i++) {
        m = 1; n = i / 2;
        for (j = 2; j <= n; j++) {
            if (i % j == 0) { m = 0; break; }
        }
        if (m) cout << i << " ";
    }
}

進階優化版（含 sqrt 與偶數排除）

#include 
#include 
void main() {
    for (int i = 2; i < 101; i++) {
        int flag = 1;
        for (int j = 2; j <= sqrt(i); j++) {
            if (i % j == 0) { flag = 0; break; }
        }
        if (flag) cout << i << endl;
    }
}

進一步優化技巧

// 排除偶數（2 以外）
if (m % 2 != 0) {
    int k = (int)sqrt(m);
    for (int n = 3; n <= k; n += 2)  // 步長 2，僅檢查奇數
        if (m % n == 0) break;
    if (n > k) { /* 是質數 */ }
}

輸出結果（1-100 質數）

2 3 5 7 11 13 17 19 23 29
31 37 41 43 47 53 59 61 67 71
73 79 83 89 97

教學重點

• 三種迴圈語法互換，邏輯不變。
• break 提前終止內層迴圈，避免多餘計算。
• sqrt 減少測試除數數量，顯著提升效能。
• 旗標變數 m/flag 記錄「是否為質數」狀態。