算法題：階乘質因數分解（n! 素因子指數統計）

算法題：階乘質因數分解（n! 素因子指數統計）

《算法競賽入門經典》5.42 題：給定 n (2≤n≤100)，將 n! 分解為素因子乘積，按素數從小到大輸出各指數。如 5! = 120 = 2^3·3^1·5^1 → 輸出 3 1 1（2,3,5 的指數）。忽略最大素因子之後的素數（否則尾部無限個 0）。

核心觀察

n! = 1×2×3×…×n。每個數分解質因子，指數累加即得 n! 的質因子分解。利用 a^m × a^n = a^(m+n)，只需統計每個素數在 1..n 中出現的總次數。

算法步驟

1. 篩法預計算 100 以內所有素數（共 25 個）。
2. 對每個輸入 n，初始化指數陣列 p[25]={0}。
3. 遍歷 i = 2..n，將 i 分解質因子，對應 p[idx]++。
4. 記錄最大非零指數下標 maxp，輸出 p[0..maxp]。

C 語言實現

#include <stdio.h>
#include <string.h>

int is_prime(int n) {
    for (int i = 2; i*i <= n; i++) if (n%i==0) return 0;
    return n > 1;
}

int prime[100], pcnt = 0;

int main() {
    for (int i = 2; i <= 100; i++) if (is_prime(i)) prime[pcnt++] = i;
    int n, p[100];
    while (scanf("%d", &n) == 1) {
        printf("%d! =", n);
        memset(p, 0, sizeof(p));
        int maxp = 0;
        for (int i = 2; i <= n; i++) {
            int m = i;
            for (int j = 0; j < pcnt; j++) {
                while (m % prime[j] == 0) {
                    m /= prime[j];
                    p[j]++;
                    if (j > maxp) maxp = j;
                }
            }
        }
        for (int i = 0; i <= maxp; i++) printf(" %d", p[i]);
        printf("\n");
    }
    return 0;
}

樣例輸入輸出

輸入:
5
53
輸出:
5! = 3 1 1
53! = 49 23 12 8 4 4 3 2 2 1 1 1 1 1 1 1

對應素數：2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53（53 以內 16 個素數）。

複雜度分析

• 素數篩選：O(100 log log 100) 忽略不計。
• 每測試用例：外層 n 循環，內層除以素數。n≤100，素數≤25，極快。
• 空間：O(1) 固定陣列。

優化思路（Legendre 公式）

素數 p 在 n! 中指數 = ⌊n/p⌋ + ⌊n/p^2⌋ + ⌊n/p^3⌋ + …。對大 n（如 10^7）極其高效，但 n≤100 直接模擬足夠。