C 語言篩選 100 以內質數：試除法實作

程式碼

#include <stdio.h>
#include <math.h>
#define N 101

int main(void) {
    int array[N], i, j, limit;

    /* 初始化：array[i] = i，0/1 稍後忽略 */
    for (i = 2; i < N; ++i) array[i] = i;

    /* 試除法標記合數 */
    for (j = 3; j < N; ++j) {
        limit = (int)sqrt(j);
        for (i = 2; i <= limit; ++i) {
            if (array[j] % i == 0) {
                array[j] = 0;  // 標記為合數
                break;
            }
        }
    }

    /* 輸出質數，每 10 個換行 */
    int cnt = 0;
    for (i = 2; i < N; ++i) {
        if (array[i]) {
            printf("%d ", array[i]);
            if (++cnt % 10 == 0) putchar('\n');
        }
    }
    if (cnt % 10) putchar('\n');
    return 0;
}

演算法說明

• 試除法：對每個數 j，只需檢測至 √j 的除數。
• 陣列標記法：用 array[j] = 0 標記合數，避免重複列印。
• 輸出格式：計數器控制每行 10 個。

優化方向

1. 改用 埃氏篩 可降至 O(n log log n)。
2. 略過偶數（2 以外），迴圈步進 2。
3. 預先建立質數表，僅用質數試除。