HDU 5108 Alexandra and Prime Numbers：最大素因子求解

HDU 5108 Alexandra and Prime Numbers：最大素因子求解

題目大意：給定 N (≤ 10⁹)，求最小 M 使 N/M 為素數。不存在輸出 0。多測試用例（≤1000），大數（>10⁶）≤100 組。

核心轉化

N/M = p (素數) → M = N/p。M 最小 ⇔ p 最大 ⇔ p 為 N 的最大素因子。

算法步驟

1. 特判 N=1 → 輸出 0。
2. 篩法預處理 10⁵ 內素數（√10⁹ ≈ 31623，取 10⁵ 保險）。
3. 對每個 N，從大到小遍歷素數表試除：
   • 若 p*p > n 則跳過（優化）。
   • 若 n % p == 0，循環除盡 n/=p，更新 max_prime = max(max_prime, p)。
4. 循環結束後，若 n > 1 剩餘大素因子，max_prime = max(max_prime, n)。
5. 答案 M = 原始N / max_prime。

代碼關鍵點（C++）

void sieve() {
    for (int i=2; i=0; --i) {
        int p=primes[i];
        if ((long long)p*p > n) continue;
        if (n%p==0) { while (n%p==0) n/=p; maxp=max(maxp,p); }
    }
    maxp = max(maxp, n);
    printf("%d\n", tmp/maxp);
}

複雜度

篩法 O(MAXP log log MAXP) ≈ 10⁵。單查詢 O(π(√N)) ≈ 3400 除法。1000 組極快。

總結

與 HDU 5108 同題（ID 206608 重複）。核心技巧：逆向思維將最小 M 轉為最大素因子，結合預篩素數表試除。注意剩餘大素因子處理與 N=1 邊界。代碼簡短高效，屬數論基礎模板題。