您现在的位置：程式碼之家 >> 編程語言 > >> 更多程式語言 >> 程式設計綜合問答

C 語言素數篩選邏輯解析：雙重循環與 j>=i 條件的數學含義

編輯：程式設計綜合問答

代碼片段


for (i = min; i <= max; i++) {
    for (j = 2; j <= i && i % j != 0; j++) 
        ; // 空循環體
    if (j >= i) 
        count++; // 統計素數
}

邏輯逐步推演

外層循環

遍歷待檢測數字 `i`，範圍 `[min, max]`。

內層循環

**尋找最小因數**：從 `j=2` 開始嘗試整除 `i`。

條件 `j <= i && i % j != 0`：
當 `j <= i` 且 `i` **不能**被 `j` 整除 → 繼續 `j++`。
**循環終止條件（二者其一）**：
1. `j > i`：已嘗試所有 `[2, i]` 內整數，**無因數** → `i` 是素數。
2. `i % j == 0`：找到因數 `j` → `i` 是合數。

`if (j >= i)` 判斷

循環結束時，若 `j >= i`（實際上只可能 `j == i` 或 `j == i+1`）：
說明循環是因 `j > i` 終止（即 `j` 達到 `i+1`），**未找到任何因數**。
結論：`i` 是素數，`count++`。

數學等價性

內層循環等價於：


boolean isPrime = true;
for (j = 2; j * j <= i; j++) { // 優化：只需試除到 sqrt(i)
    if (i % j == 0) { isPrime = false; break; }
}
if (isPrime) count++;

原代碼 `j <= i` 未優化，效率較低（O(n²)），但邏輯正確。

關鍵點總結

`j >= i` 含義：標記「試除完畢無因數」，即素數判定條件。
循環終止邏輯：`for` 循環條件為「繼續條件」，否則終止。`i % j != 0` 為假(即整除)時終止，此時 `j < i`，不滿足 `j >= i`。
優化方向：內層循環條件改為 `j * j <= i`，大幅降低複雜度至 O(n√n)。

完整優化版代碼


#include 
#include 

int countPrimes(int min, int max) {
    int count = 0;
    for (int i = min; i <= max; i++) {
        if (i < 2) continue; // 0,1 非素數
        int isPrime = 1;
        for (int j = 2; j * j <= i; j++) {
            if (i % j == 0) { isPrime = 0; break; }
        }
        if (isPrime) count++;
    }
    return count;
}

int main() {
    printf("100 以內素數個數: %d\n", countPrimes(2, 100)); // 25
    return 0;
}