解题思路

求 n 最多能分解成多少个互不相同的素数的和。

思路：回溯。

1. 先把 2~n 的所有素数收集起来
2. 用回溯逐个考虑每个素数：选它还是不选它
   • 选：总和加上这个素数，用的素数个数加 1
   • 不选：跳过这个素数
3. 当总和正好等于 n 时，记录用的素数个数，取最大值
4. 如果总和超过 n 或素数用完了，就停止

为什么要互不相同？ 题目要求分解成互不相同的素数，所以每个素数只能选一次，这就是选或不选两种选择。

举例：n=21

• 21 = 2+3+5+11，用了 4 个素数
• 这是分解成最多素数的方法

参考代码

#include <iostream>
#include <cmath>
using namespace std;

int zs[50], l;
int n, maxn = 0;

bool ss(int x) {
    if (x < 2) return false;
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) return false;
    }
    return true;
}

void fun(int k, int s, int zh) {
    if (s == n) {
        if (zh > maxn) maxn = zh;
        return;
    }
    if (s > n || k >= l) return;

    fun(k + 1, s + zs[k], zh + 1);  // 选这个素数
    fun(k + 1, s, zh);              // 不选
}

int main() {
    cin >> n;
    for (int i = 2; i <= n; i++) {
        if (ss(i)) zs[l++] = i;
    }
    fun(0, 0, 0);
    cout << maxn;
    return 0;
}

复杂度分析

• 时间复杂度：O(2^P)，P 为素数个数
• 空间复杂度：O(P)，递归深度