C 語言尋找質數：埃拉托斯特尼篩法變體實作 (0~100)

編輯：關於C語言

演算法思路

陣列標記法：建立大小 N 陣列，索引即數字。初始化每個索引為自身值。從 2 開始，若該索引值非 0 (即為質數)，則將其所有倍數標記為 0。最後遍歷陣列，非 0 者即質數。本範例使用 sqrt(n) 優化內層迴圈上限。

完整程式碼

#include 
#include 
#define N 101

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

    // 初始化：array[i] = i
    for (i = 2; i < N; i++) array[i] = i;

    // 篩選：對每個數 j，檢查 2~sqrt(j) 是否能整除
    for (j = 3; j < N; j++) {
        tmp_sqrt_N = sqrt(j);
        for (i = 2; i <= tmp_sqrt_N; i++) {
            if (array[j] % i == 0) { // 被整除 → 非質數
                array[j] = 0;
                break; // 關鍵：找到因子即跳出，避免多次標記
            }
        }
    }

    // 輸出：每行 10 個
    int count = 0;
    for (i = 2; i < N; i++) {
        if (array[i] != 0) {
            printf("%d ", array[i]);
            if (++count == 10) { printf("\n"); count = 0; }
        }
    }
    if (count != 0) printf("\n");
    return 0;
}

執行結果

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

質數篩選輸出畫面

演算法複雜度分析

時間：O(N √N) — 外層 N，內層 √N。標準埃拉托斯特尼篩法為 O(N log log N) (標記倍數而非試除)，效能更優
空間：O(N)

標準篩法優化版 (O(N log log N))

void sieve(int n) {
    bool is_prime[n+1];
    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);
}

關鍵差異：從 i*i 開始標記、步長為 i、使用布林陣列而非整數陣列。