题目描述
已知 n个整数x1,x2,…,xn，以及1个整数k(k<n)。从nn个整数中任选kk个整数相加，可分别得到一系列的和。
例如当n=4,k=3,4个整数分别为3,7,12,19时，可得全部的组合与它们的和为：
3+7+12=22
3+7+19=29
7+12+19=3
3+12+19=34
现在，要求你计算出和为素数共有多少种。
例如上例，只有一种的和为素数：3+7+19=29
输入输出格式
输入格式：
键盘输入，格式为：
n,k(1≤n≤20,k<n)
x1,x2,…,xn(1≤xi≤5000000)
输出格式：
屏幕输出，格式为：1个整数（满足条件的种数）。
输入输出样例
输入样例：
4 3
3 7 12 19
输出样例：
1
1.首先要说说如何判断质数，判断质数最通俗易懂的办法就是：
对于一个小于num的正整数x，如果num不能整除x，则num必然不能整除num/x （num = num/x * x）。反之相同。我们又知num =√num*√num。 如果n除以大于√num的数，必得到小于√num的商，而小于√num的整数已经在2到√num的整数试过了，因为就没有必要再试（√num, num）范围内的数了。代码如下：
注：经常会看到别人说“一个数 n 如果是合数，那么它的所有的因子不超过sqrt(n)”。这句话是错误的。举一个例子，16的因子包括了1、2、4、8，但很明显8>√16。另外，因子跟因数是不一样的，因数还会包括数本身，如16的因数为1、2、4、8、16。
所以我们可以这样实现：
#include<cstdio>
#include<cmath>
bool ask(int x)
{
for (int i = 1 ; i <= sqrt(x) ;i ++){
if(x % i == 0){
return 0;
}
}
return 1;
}
2。由于这个题的n非常小只有20，我们考虑搜索直接暴力。
分析题意可知本题适合用深搜。
深搜代码如下：
void dfs(int step ,int sum,int cnt)
{//step为总次数，sum为当前所选数的总和 cnt为当前选的数
if(step == n+ || cnt == k){
if(cnt == k && ask(sum)){
ans ++;
}
return;
}
dfs(step + ,sum +a[i],cnt+); //选择下一个数
dfs(step + ,sum ,cnt) //不选择下一个数
return;
}
总代码：
#include <cstdio>
#include <cmath>
int n,k;
int ans;
const int N = ;
int K[N];
bool ask(int x)
{
for (int i = ;i <= sqrt(x);i ++){
if(x % i == ){
return ;
}
}
return ;
}
void dfs(int step,int sum,int cnt)
{ if((step == (n + ) )|| (cnt == k)){
if (ask(sum) && cnt == k){
ans ++;
}
return;
}
dfs(step+,sum + K[step],cnt +);//选择下个数的情况
dfs(step+,sum,cnt); //不选择下个数的情况
return;
}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
scanf("%d%d",&n,&k);
for (int i = ;i <= n; i ++){
scanf("%d",&K[i]);
}
dfs(,,);
printf("%d",ans);
// fclose(stdin);
// fclose(stdout);
return ;
}