C 語言求指定範圍內的質數（素數）

問題描述

輸入兩個整數 a、b，輸出區間 [a, b] 內所有的質數。質數定義為大於 1 且僅能被 1 與自身整除的自然數。

基礎試除法實作

#include 

int main() {
    int a, b, i, j;
    printf("請輸入整數範圍並用空格隔開：\n");
    scanf("%d %d", &a, &b);

    for (i = a; i <= b; i++) {
        for (j = 2; j <= i - 1; j++) {
            if (i % j == 0) break;  /* 找到因子，非質數 */
        }
        if (j >= i - 1)             /* 迴圈正常結束，未找到因子 */
            printf("%d ", i);
    }
    return 0;
}

效能優化要點

• 試除上限優化：`j <= i-1` 可改為 `j * j <= i`（或 `j <= sqrt(i)`），將內層迴圈從 O(n) 降為 O(√n)。
• 跳過偶數：2 以外的偶數必合數，外層迴圈可步進 2。
• 篩法預處理：若多次查詢或範圍較大，建議使用埃拉托斯特尼篩法（Sieve of Eratosthenes）一次性生成質數表，查詢複雜度降為 O(1)。

優化版範例（試除 √n）

for (i = a; i <= b; i++) {
    if (i < 2) continue;
    int is_prime = 1;
    for (j = 2; j * j <= i; j++) {
        if (i % j == 0) { is_prime = 0; break; }
    }
    if (is_prime) printf("%d ", i);
}

複雜度對比