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

篩法找質數完整教學

埃拉托斯特尼篩法是尋找一定範圍內所有質數的經典演算法，本文將示範如何用 C 語言實作此演算法，找出 10000 以內的所有質數並輸出。

問題描述

使用篩法找出 10000 以內的所有質數。篩法核心邏輯：建立布林陣列標記各數字是否為質數，從 2 開始將其倍數標記為合數，剩下未被標記的即為質數。

演算法步驟

1. 定義常數 NUM 10000，宣告整數陣列 a[NUM] 初始化為 0。
2. 將索引 2 到 9999 的元素設為 1（暫視為質數候選）。
3. 遍歷陣列，若 a[i] == 1 則印出 i 為質數，並將 i 的所有倍數標記為 0（合數）。
4. 注意：內層迴圈從 j = i 開始，步長為 i，並檢查 j % i == 0 才標記，雖然多此一舉但邏輯正確。

完整程式碼

/* 程式標頭註解 */
#include <stdio.h>

#define NUM 10000

int main()
{
    int i;
    int j;
    int a[NUM] = {0};

    for(i = 2; i < NUM; i++)  // 0、1 不是質數，跳過
    {
        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 開始，步長為 i，無需檢查 j % i == 0。
• 使用位元陣列或 bool 型別可節省記憶體。