C語言實作埃拉托斯特尼篩法求 10000 以內所有質數

經典的質數篩選演算法：建立布林陣列標記 0~9999，初始假設全為質數（1），0 與 1 標記為非質數。從 2 開始，若為質數則印出，並將其所有倍數標記為非質數。時間複雜度 O(n log log n)。

演算法步驟

1. 陣列 a[10000] 全置 1，a[0]=a[1]=0。
2. 外層迴圈 i=2..9999：若 a[i]==1 則為質數，列印。
3. 內層迴圈 j=i; j<10000; j+=i：將倍數標記 0。

程式碼

#include <stdio.h>
#define NUM 10000

int main() {
    int i, j, a[NUM] = {0};
    for (i = 2; i < NUM; i++) a[i] = 1;

    for (i = 0; i < NUM; i++) {
        if (a[i] == 1) {
            printf("%4d為質數.\n", i);
            for (j = i; j < NUM; j += i)
                if (j % i == 0) a[j] = 0;
        }
    }
    return 0;
}

優化細節

• 外層只需跑到 sqrt(NUM)。
• 內層從 i*i 開始更高效。
• 位元陣列可節省記憶體。