趣味數學題：將正整數拆分為質數之和，使乘積最大化

問題描述

給定正整數 n，將其拆分為若干質數之和（可重複使用質數），使這些質數的乘積最大。輸出最大乘積。

例如：n = 14，質數集合 {2,3,5,7,11,13}。最優拆分為 3+3+3+5=14，乘積 3×3×3×5=135。

動態規劃解法

狀態定義

dp[i] 表示和為 i 時的最大乘積。質數集合 primes 為所有 ≤ n 的質數。

轉移方程

dp[i] = max(dp[i], dp[i - p] * p) 對所有 p ∈ primes, p ≤ i

初始 dp[0] = 1（空乘積），其餘 0。按 i = 1..n 遞推。

完整 C++ 代碼

#include <bits/stdc++.h>
using namespace std;

vector<int> sieve(int n) {
    vector<bool> is_prime(n+1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i*i <= n; ++i)
        if (is_prime[i])
            for (int j = i*i; j <= n; j += i) is_prime[j] = false;
    vector<int> primes;
    for (int i = 2; i <= n; ++i) if (is_prime[i]) primes.push_back(i);
    return primes;
}

int main() {
    int n;
    if (!(cin >> n)) return 0;
    auto primes = sieve(n);

    vector<long long> dp(n+1, 0);
    dp[0] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int p : primes) {
            if (p > i) break;
            dp[i] = max(dp[i], dp[i-p] * p);
        }
    }
    cout << dp[n] << '\n';
    return 0;
}

數學洞見：貪心策略

經分析，盡可能多用 3，餘數處理如下：

• n % 3 == 0：全用 3。
• n % 3 == 1：拿出兩個 3 換成兩個 2（即 3+1 → 2+2）。
• n % 3 == 2：用一個 2，其餘全 3。

因 3×3 > 2×2×2 且 3 > 2，3 是「性價比」最高的質數。貪心法 O(1) 時間，但 DP 更通用（質數集合可變）。

複雜度

• 篩法生成質數：O(n log log n)
• DP 主循環：O(n × π(n)) ≈ O(n²/log n)
• 空間：O(n)

對於 n ≤ 10⁴ 即時可解；更大 n 建議貪心或矩陣快速冪優化。