您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> 關於C

C語言求1000以內質數：試除法優化與常見錯誤分析

編輯：關於C

題目要求

輸出100到1000之間的所有質數（素數），即只能被1和自身整除的正整數。

原代碼問題分析

原始代碼中的zhishu()函數存在嚴重邏輯缺陷：

int zhishu(int a) {
    for (int j = 2; j <= a; j++) {  // 錯誤：j 遍歷到 a 本身
        if (a % j == 0) return 0;   // 當 j == a 時必定整除，導致所有數都被判為非質數
    }
    return 1;
}

此邏輯會導致無任何輸出，因為所有數都會被誤判為合數。

正確實現（試除法優化版）

#include <stdio.h>
#include <math.h>  // 需引入 sqrt()

// 判斷質數：優化至 √n
int is_prime(int n) {
    if (n <= 1) return 0;
    if (n == 2) return 1;        // 2 是唯一的偶質數
    if (n % 2 == 0) return 0;    // 排除其他偶數

    int limit = (int)sqrt(n);    // 只需檢查到 √n
    for (int i = 3; i <= limit; i += 2) {  // 步長 2，跳過偶數
        if (n % i == 0) return 0;
    }
    return 1;
}

int main() {
    printf("100-1000 之間的質數：\n");
    int count = 0;
    for (int i = 100; i <= 1000; i++) {
        if (is_prime(i)) {
            printf("%4d", i);
            if (++count % 10 == 0) putchar('\n');  // 每行 10 個
        }
    }
    if (count % 10 != 0) putchar('\n');
    printf("共找到 %d 個質數\n", count);
    return 0;
}

核心優化點解析

優化策略	原理	效能提升
判斷上限 √n	若 n = a×b，則 a≤√n 或 b≤√n	從 O(n) 降至 O(√n)
預先排除偶數	除 2 外無偶質數	減少 50% 迭代次數
步長為 2	只檢查奇數因子	再減少 50% 檢查次數

進階算法：埃拉托斯特尼篩法

若需頻繁查詢範圍內質數，篩法效率更高（O(n log log n)）：

void sieve(int limit) {
    bool *is_prime = calloc(limit + 1, sizeof(bool));
    for (int i = 2; i <= limit; i++) is_prime[i] = true;

    for (int p = 2; p * p <= limit; p++) {
        if (is_prime[p]) {
            for (int m = p * p; m <= limit; m += p)
                is_prime[m] = false;
        }
    }
    // 輸出 100-1000 區間質數
    for (int i = 100; i <= 1000; i++)
        if (is_prime[i]) printf("%d ", i);
    free(is_prime);
}