C 語言遞迴實作質因數分解：不使用迴圈的完整程式碼與邏輯詳解 C 語言遞迴實作質因數分解：不使用迴圈的完整程式碼與邏輯詳解

題目要求

• C 語言
• 遞迴演算法
• 質因數分解 (如 54 = 2 × 3 × 3 × 3)
• 不得使用迴圈

核心邏輯：雙重遞迴

1. 質數判斷遞迴：`isPrime(n, divisor)` 從 `n-1` 遞減測試除數
2. 分解主遞迴：`factorize(n, candidate)` 從 `n` 遞減嘗試除數，找到質因數後輸出並遞迴處理商

完整程式碼 (修正原回答邏輯錯誤，增加邊界處理)

#include 

/**
 * 遞迴判斷質數
 * @param n 待測數
 * @param d 當前測試除數 (初始呼叫傳 n-1)
 * @return 1=質數, 0=合數
 */
int isPrime(int n, int d) {
    if (n <= 1) return 0;
    if (d == 1) return 1;           // 測試完所有除數，無法整除 → 質數
    if (n % d == 0) return 0;       // 能被整除 → 合數
    return isPrime(n, d - 1);       // 測試下一個除數
}

/**
 * 遞迴質因數分解並輸出
 * @param n 待分解數
 * @param d 當前候選除數 (初始呼叫傳 n)
 */
void factorize(int n, int d) {
    if (n <= 1) return;             // 分解完成

    // 找到質因數且商為 1 (最後一個因數)
    if (n % d == 0 && isPrime(d, d - 1) && n == d) {
        printf("%d", d);
        return;
    }

    // 找到質因數 (非最後一個)
    if (n % d == 0 && isPrime(d, d - 1)) {
        printf("%d*", d);
        factorize(n / d, d);        // 繼續分解商，從同一除數開始 (處理重複因數)
        return;
    }

    // 當前除數不行，嘗試下一個較小除數
    factorize(n, d - 1);
}

int main() {
    int n = 54;
    printf("%d = ", n);
    factorize(n, n);
    printf("\n");
    return 0;
}

執行流程追蹤 (n=54)

輸出結果

54 = 3*3*3*2

關鍵設計點解析

• 從大到小試除：`d` 從 `n` 遞減至 2，符合遞迴自然順序
• 重複因數處理：找到因數 `d` 後遞迴呼叫 `factorize(n/d, d)` **保持同一 `d`**，可連續分解多次相同質因數 (如 3³)
• 格式控制：最後一個因數不印 `*`，透過 `n == d` 判斷
• 質數判斷優化：`isPrime` 只需測試到 `sqrt(n)`，但為符合「無迴圈」改用遞減遞迴 (教學妥協)

複雜度與限制

• 時間：O(n²) 極其低效 (質數判斷 O(n) × 試除 O(n))，僅適合極小數值教學
• 空間：O(n) 遞迴深度，大數會堆疊溢位
• 實務替代：試除法迴圈優化至 `sqrt(n)`、Pollard's Rho、二次篩法

總結

雙重遞迴 (質數判斷 + 分解主流程) 可在無迴圈限制下實作質因數分解。關鍵在於**找到因數後保持除數不變遞迴處理商**以支援重複質因數。此解法僅供演算法教學理解遞迴替代迴圈，**生產環境嚴禁使用**。