已知 n 个整数x1,x2,…,xn，以及1个整数k(k<n)。从n个整数中任选k个整数相加，可分别得到一系列的和。例如当n=4,k=3,4个整数分别为3,7,12,19时，可得全部的组合与它们的和为： 3+7+12=22 3+7+19=29 7+12+19=38 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、使用DFS深搜，思路简单，见代码。 2、使用next_permutation()来进行处理，另外设置一个新的数组来判断是否选取了该数字，具体实现见代码。
1、DFS深搜 具体解释见注释：
#include<bits/stdc++.h> using namespace std; int a[30]; int b[30]; int m,k; int sum=0; inline bool check(int ans) { if(ans==0||ans==1) return false;//二者就是质数，也不是合数 for(int i=2;i<=sqrt(ans);i++) { if(ans%i==0) return false;//2是素数 } return true; } void dfs(int n,int ans,int j)//n代表当前选取了几个数，ans代表当前选取了的数字的和，j代表从j下标开始继续选取数字 {//默认数据是从小到大排序的，也就是说选取的后面的数字一定大于前面的数字 if(n==k)//如果已经选取了k个数，判断是否是素数之后输出 { if(check(ans)) sum++; return ; } for(int i=j;i<=m;i++) { if(b[i]==0)//如果没有选取过 { b[i]=1; dfs(n+1,ans+a[i],i+1);//一定是i+1,表示当前坐标的下一个 b[i]=0;//恢复状态 } } return ; } int main() { scanf("%d %d",&m,&k); for(int i=1;i<=m;i++) { scanf("%d",&a[i]); } dfs(0,0,1);//刚开始选取了0个数字，和为0，从1下标开始进行选取 printf("%d",sum); return 0; }2、STL中next_permutation()
#include<bits/stdc++.h> using namespace std; int a[30]; int b[30]; int m,k; int sum=0; inline bool check(int ans) { if(ans==0||ans==1) return false;//二者就是质数，也不是合数 for(int i=2;i<=sqrt(ans);i++) { if(ans%i==0) return false;//2是素数 } return true; } int main() { scanf("%d %d",&m,&k); for(int i=1;i<=m;i++) { scanf("%d",&a[i]); b[i]=1; } for(int i=1;i<=k;i++) { b[i]=0;//需要选取几位就让前几位为0 } int sum=0; int ans=0; do{ int ans=0; for(int i=1;i<=m;i++) { if(b[i]==0) ans+=a[i];//如果为0说明被选中 } if(check(ans)) sum++;//判断是否是素数 } while(next_permutation(b+1,b+m+1)); printf("%d",sum); return 0; }