C語言實作：找出200以內所有質數（優化版試除法）

質數篩選：200以內質數列表

本程式使用優化的試除法找出 200 以內所有質數。利用「偶數不為質數（除2）」與「只需試除到 sqrt(n) 或 n/2」兩項優化，大幅減少判斷次數。

演算法邏輯

1. 直接輸出 2（唯一偶質數）。
2. 外層迴圈遍歷奇數：num = 2*i - 1 (i=1..100)，產生 1,3,5...199。
3. 跳過 1（非質數），從 3 開始判斷。
4. 內層迴圈 j = 2 到 num/2，若 num % j == 0 則為合數，標記 flag=0 並 break。
5. 若迴圈結束 flag 仍為 1，則為質數，輸出。

完整程式碼

#include <stdio.h>

int main()
{
    int i, j, flag, num;

    printf("%3d是質數.\n", 2);  // 2 是唯一偶質數

    for(i = 1; 2*i - 1 <= 200; i++)  // 遍歷奇數
    {
        num = 2*i - 1;
        if(num > 2)
        {
            flag = 1;
            for(j = 2; j < num/2; j++)
            {
                if(num % j == 0)
                {
                    flag = 0;
                    break;
                }
            }
            if(flag == 1)
                printf("%3d是質數.\n", num);
        }
    }
    return 0;
}

執行結果示意

輸出質數列表（200以內共46個）

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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199

優化建議

• 內層迴圈上限改為 j*j <= num (即 sqrt(num))，更少迴圈次數。
• 只用質數做試除（需先建質數表），進一步加速。
• 若需大範圍質數，改用埃拉托斯特尼篩法 O(n log log n) 更快。
• 將 2 納入迴圈統一處理：for(num=2; num<=200; num++) 內部特判偶數。

時間複雜度

當前：O(n × n/2) ≈ O(n²/2)。優化後：O(n × √n) 或篩法 O(n log log n)。