C 語言遞迴實現 100 以內質數篩選：完整代碼與算法解析

題目需求

• C 語言實現
• 輸出 100 以內所有質數
• 必須使用遞迴（無迴圈限制隱含）

算法選擇：遞迴版試除法

對每個候選數 n (2..100)，遞迴檢查是否存在因數 d (2..√n)。

完整可編譯代碼

#include 
#include 

/* 遞迴判斷 n 是否為質數
   n: 待測數
   d: 當前試除數 (從 2 開始)
   返回：1=質數, 0=合數 */
int is_prime_rec(int n, int d) {
    if (d > (int)sqrt(n)) return 1;          // 終止條件：超過 √n
    if (n % d == 0) return 0;                // 找到因數 → 合數
    return is_prime_rec(n, d + 1);           // 遞迴試下一個因數
}

/* 遞迴遍歷 2..100 並列印質數 */
void print_primes_rec(int current) {
    if (current > 100) return;               // 終止條件
    if (is_prime_rec(current, 2))
        printf("%d ", current);
    print_primes_rec(current + 1);           // 遞迴處理下一個數
}

int main() {
    printf("100 以內的質數：\n");
    print_primes_rec(2);
    printf("\n");
    return 0;
}

執行結果

100 以內的質數：
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

關鍵點解析

1. 雙層遞迴：外層遍歷候選數（2→100），內層試除判斷質數。
2. 終止條件精確：
   • 外層：current > 100
   • 內層：d > sqrt(n)（避免浮點誤差可用 d*d > n）
3. 堆疊深度安全：最大遞迴深度 ≈ 100 (外層) + 10 (內層 √100) = 110，遠小於堆疊限制。
4. 無任何迴圈關鍵字：純遞迴實現，符合嚴格題目要求。

進階優化：遞迴版埃拉托斯特尼篩法（較難）

傳統篩法依賴迴圈標記倍數，純遞迴實現需維護動態陣列與索引，代碼複雜度大幅上升，教學價值有限，不建議在基礎課程採用。

參考資源

百度知道：C語言遞迴求質數參考代碼

最佳回答提供的連結可作為補充參考，本文給出的代碼經測試可直接編譯執行（GCC/MSVC/Clang 皆可）。