C 語言經典算法：尋找等於各位數字階乘和的三位數（因子數）

C 語言經典算法：尋找等於各位數字階乘和的三位數（因子數）

因子數 是指一個數等於其各位數字階乘之和。已知只有四個十進制因子數：1, 2, 145, 40585。本文實現三位數範圍內（100-999）的枚舉查找，核心為階乘函數與位數分解。

算法步驟

1. 編寫階乘函數 J(n) 計算 n!（n ≤ 9，結果可預計算優化）。
2. 枚舉 100 到 999 每個整數 s。
3. 分解個、十、百位：ge = s%10; shi = s/10%10; bai = s/100;
4. 判斷 s == J(ge) + J(shi) + J(bai)，滿足則輸出。

完整代碼

#include 

// 階乘函數（可優化為查表）
int J(int n) {
    int t = 1;
    for (int i = 1; i <= n; i++) t *= i;
    return t;
}

int main() {
    for (int s = 100; s < 1000; s++) {
        int ge = s % 10;
        int shi = s / 10 % 10;
        int bai = s / 100;
        if (s == J(ge) + J(shi) + J(bai)) {
            printf("%d = %d! + %d! + %d!\n", s, bai, shi, ge);
        }
    }
    return 0;
}

運行結果

145 = 1! + 4! + 5!

優化方向

• 查表法：預計算 0!~9! 存入數組 fact[10]，O(1) 獲取，消除重複計算。
• 提前剪枝：最大三位數 999，三個 9 階乘和 3×362880=1088640 > 999，無剪枝空間；但可限制百位 ≤ 2（因 3!×3=18 < 300）。
• 擴展至 N 位：結合位數上界分析（n×9! < 10^n）確定搜索上限。

數學延伸

因子數在不同進制下定義不同，十進制僅有 4 個（含 1, 2）。此題常作為「枚舉+分解+函數封裝」綜合訓練題。