C 語言求 1-100 素數的五種經典演算法實現與效能對比

演算法一：試除法（基礎版）

#include <stdio.h>
#include <math.h>

int main() {
    for (int i = 2; i <= 100; i++) {
        int isPrime = 1;
        for (int j = 2; j <= sqrt(i); j++) {
            if (i % j == 0) { isPrime = 0; break; }
        }
        if (isPrime) printf("%d ", i);
    }
    return 0;
}

時間複雜度：O(n√n)，適合教學與小範圍。

演算法二：優化試除法（僅試除質數）

int primes[100], cnt = 0;
for (int i = 2; i <= 100; i++) {
    int isPrime = 1;
    for (int j = 0; j < cnt && primes[j] * primes[j] <= i; j++) {
        if (i % primes[j] == 0) { isPrime = 0; break; }
    }
    if (isPrime) primes[cnt++] = i;
}

減少除法次數，利用已找到的質數作為除數。

演算法三：埃拉托斯特尼篩法

#define MAX 100
int isComposite[MAX + 1] = {0};
for (int i = 2; i * i <= MAX; i++) {
    if (!isComposite[i]) {
        for (int j = i * i; j <= MAX; j += i)
            isComposite[j] = 1;
    }
}
for (int i = 2; i <= MAX; i++)
    if (!isComposite[i]) printf("%d ", i);

時間複雜度 O(n log log n)，空間 O(n)，百萬級範圍首選。

演算法四：線性篩

int primes[MAX], cnt = 0;
int minFactor[MAX + 1] = {0};
for (int i = 2; i <= MAX; i++) {
    if (minFactor[i] == 0) {
        minFactor[i] = i;
        primes[cnt++] = i;
    }
    for (int j = 0; j < cnt && primes[j] <= minFactor[i] && i * primes[j] <= MAX; j++)
        minFactor[i * primes[j]] = primes[j];
}

每個合數僅被最小質因子篩一次，嚴格 O(n)，適合需質因子分解的場景。

演算法五：位元組優化篩（節省記憶體）

// 僅存儲奇數，位元組每位代表一個奇數
#define MAX 100
unsigned char sieve[(MAX >> 4) + 1] = {0};
#define IS_COMPOSITE(x) (sieve[(x)>>4] & (1 << (((x)>>1)&7)))
#define SET_COMPOSITE(x) (sieve[(x)>>4] |= (1 << (((x)>>1)&7)))

for (int i = 3; i * i <= MAX; i += 2)
    if (!IS_COMPOSITE(i))
        for (int j = i * i; j <= MAX; j += i << 1)
            SET_COMPOSITE(j);

printf("2 ");
for (int i = 3; i <= MAX; i += 2)
    if (!IS_COMPOSITE(i)) printf("%d ", i);

記憶體降低 8 倍，適合嵌入式環境或極大範圍（10^8+）。

效能對比表（100 以內測試參考）

常見錯誤避坑

• 篩法外層循環條件寫成 i <= MAX 導致重複標記。
• 內層起始點未用 i*i 而用 2*i，效率大幅下降。
• 未處理 2 為唯一偶質數，導致奇數優化邏輯出錯。

最佳實踐建議

1. 範圍 < 10^6：直接用埃氏篩，代碼最簡潔。
2. 範圍 10^6 ~ 10^8：線性篩或位元組優化篩。
3. 需單次判斷大數質數：Miller-Rabin 概率測試。
4. 嵌入式開發：預計算質數表燒錄 Flash，運行期直接查表。