自动搬运

查看原文

来自洛谷，原作者为

	Sweet_2013 今夕是何年？ | 234粉爆我妹的照片，求关 | 互关条件 /training/813543

搬运于2025-08-24 21:17:22，当前版本为作者最后更新于2025-03-03 21:41:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我的解题思路

我们可以使用 dfs（深度优先搜索）来节约这个问题，我们需要按照以下步骤解决这个问题：

• 定义变量：$k$ 用于记录素数的数量，$ans$ 用于记录分解的最大加数个数。
• 由于 $n$ 的范围仅有 $200$，所以定义数组 $p$，用于存储 $1-200$ 范围内的素数，判断哪些是素数。
• 进行 dfs，有以下操作：
  • $step$ 用于计算当前递归的步骤，$s$ 表示当前的累加和，$num$ 用于计算当前的加数的个数。
  • 如果如果当前累加和 $s$ 超过了目标值 $n$，则直接返回，因为这种情况下不可能找到合法的分解方案。
  • 如果当前累加和 $s$ 等于目标值 $n$，更新答案 $ans$，取当前加数个数 $num$ 和已知的最大加数个数 $ans$ 中的较大值并返回上一层递归。
  • 如果当前步骤 $step$ 超过了素数数组的大小 $k+1$，则直接返回，因为没有更多的素数可以使用。
  • 跳过当前素数，不将其加入累加和中，继续尝试下一个素数；然后将当前素数 $p_{step}$ 加入累加和中，并将加数个数加 $1$，继续尝试下一个素数。
• dfs 结束，输出答案。

上代码！

#include<bits/stdc++.h>
using namespace std;
int n, p[201], k, ans;
bool ss(int n){
	if(n==1) return false;
	for(int i=2;i<=sqrt(n);i++) if(n%i==0) return false;
	return true;
}//判断素数的函数。
void dfs(int step, int s, int num){
	if(s>n) return ;//如果当前累加和 s 超过了目标值 n，那么返回。
	if(s==n){
		ans=max(ans,num);
		return ;
	}//如果当前累加和 s 等于目标值 n，更新答案 ans，取当前加数个数 num 和已知的最大加数个数 ans 中的较大值，返回上一层递归。
	if(step==k+1) return ;//如果当前步骤 step 超过了素数数组的大小（即 k+1），那么直接返回。
	dfs(step+1,s,num);//跳过当前素数，不将其加入累加和中，继续尝试下一个素数。
	dfs(step+1,s+p[step],num+1);//递归调用 dfs 函数，将当前素数加入累加和中，并将加数个数加 1，继续尝试下一个素数。
}
int main(){
	cin>> n;
	for(int i=2;i<=200;i++) if(ss(i)==true) p[++k]=i;//找 2——200 之间的所有素数，并将它们存储在数组 p 中。变量 k 用于记录素数的数量。
	dfs(1,0,0);//用 dfs 函数，从第一个素数开始，初始累加和为 0，初始加数个数为 0。
	cout<<ans;//输出答案。
	return 0;
}