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

埃拉托斯特尼篩法求素數：C語言實現中循環變量作用域錯誤修復與算法優化

編輯：C 語言問答

原代碼致命錯誤


for (i = 0; i <= 999; i++) x[i] = i+1;
x[0] = 0;
for (j = 1; j <= 999; j++) {
    if (x[i] != 0) {  // ❌ i 為 1000，越界訪問 x[1000]
        for (i = j+1; i <= 999; i++)  // ❌ 修改外層循環變量 i
            if (x[i] % x[j] == 0) x[i] = 0;
    }
}

錯誤本質

第一個循環結束後 i = 1000（數組長度 N=1000，有效索引 0-999）
if (x[i] != 0) 訪問 x[1000] → **緩衝區溢出**，未定義行為
內層循環復用 i 破壞外層邏輯

標準篩法正確實現


#include 
#include 
#include 

#define N 1000

int main() {
    bool is_prime[N+1];
    for (int i = 0; i <= N; i++) is_prime[i] = true;
    is_prime[0] = is_prime[1] = false;
    
    for (int p = 2; p * p <= N; p++) {  // 優化：只需篩到 sqrt(N)
        if (is_prime[p]) {
            for (int multiple = p * p; multiple <= N; multiple += p)  // 從 p² 開始
                is_prime[multiple] = false;
        }
    }
    
    printf("Primes up to %d:\n", N);
    for (int i = 2; i <= N; i++)
        if (is_prime[i]) printf("%d ", i);
    printf("\n");
    return 0;
}

關鍵優化點

優化	原始	改進	效果
外層循環上限	N	√N	減少 ~68% 迭代
內層起始點	j+1	p²	避免重複標記
數據類型	int 數組存值	bool 數組標記	內存節省 75%，語義清晰
變量作用域	外部共用 i,j	for 循環內部聲明 (C99)	避免變量污染，可讀性強

進階：位圖篩法（Bitwise Sieve）


// 僅存儲奇數，每位代表一個數，內存再減半
#define MAX 1000000
unsigned char sieve[MAX/16+1];  // 每字節存8個奇數

#define IS_COMPOSITE(x) (sieve[(x)>>4] & (1<<((x>>1)&7)))
#define SET_COMPOSITE(x) (sieve[(x)>>4] |= (1<<((x>>1)&7)))

篩法是數論與算法課程的經典入門，**變量作用域隔離**與**邊界條件精確控制**是避免低級錯誤的關鍵。