题解：B4141 [信息与未来 2016] 素数分解
Sweet_2013 · · 题解
我的解题思路
我们可以使用 dfs（深度优先搜索）来节约这个问题，我们需要按照以下步骤解决这个问题：
- 定义变量：
k 用于记录素数的数量，ans 用于记录分解的最大加数个数。 - 由于
n 的范围仅有200 ，所以定义数组p ，用于存储1-200 范围内的素数，判断哪些是素数。 - 进行 dfs，有以下操作：
-
- 如果如果当前累加和
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;
}