HDU 1164 Eddy's Research I：質因數分解入門

問題背景

給定一個整數 x (1 < x ≤ 65535)，將其分解為質因數乘積形式輸出。例如 9412 = 2×2×13×181。這是經典的質因數分解問題，數據範圍較小，適合用篩法預處理質數表。

算法思路

1. 埃氏篩預處理質數：建立長度 65536 的布爾數組 isPrime，標記所有質數。時間 O(N log log N)。
2. 試除法分解：對每個輸入 n，從小到大遍歷質數 p，當 p·p > n 時停止。若 p 能整除 n，反覆除以 p 並記錄，直到不能整除。
3. 處理剩餘大質數：循環結束後若 n > 1，說明剩餘的 n 本身是質數，直接加入結果。
4. 格式化輸出：用 * 連接所有質因子，按非遞減序輸出。

代碼實現要點

const int MAXN = 65536;
bool isPrime[MAXN];
vector primes;

void sieve() {
    fill(isPrime, isPrime + MAXN, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i * i < MAXN; ++i)
        if (isPrime[i])
            for (int j = i * i; j < MAXN; j += i)
                isPrime[j] = false;
    for (int i = 2; i < MAXN; ++i)
        if (isPrime[i]) primes.push_back(i);
}

void factorize(int n) {
    vector factors;
    for (int p : primes) {
        if (p * p > n) break;
        while (n % p == 0) {
            factors.push_back(p);
            n /= p;
        }
    }
    if (n > 1) factors.push_back(n);
    // 輸出
    for (size_t i = 0; i < factors.size(); ++i) {
        if (i) cout << '*';
        cout << factors[i];
    }
    cout << '\n';
}

複雜度分析

• 預處理：O(MAXN log log MAXN) ≈ 65536 × 小常數，極快。
• 單次分解：O(√n / log n) 質數個數，n ≤ 65535 時最多約 60 個質數試除，瞬間完成。

總結

HDU 1164 是質因數分解的入門題，核心在於「預處理質數表 + 試除法」。掌握埃氏篩與分解邏輯，對後續處理更大數值（如 Pollard-Rho）打下基礎。