取数组合——判断素数

前言：

马上ACM要考核了，我也开始复习我在OJ上做过的门槛题，看到了这个挺难的题，说实话，当时我没写出来这道题，我还是去社区搜了一下才找到解法的，要用到DFS，属于数据结构图论里面的算法，确实比较难。

Description

组长特别想让小学妹进组，但是现在在所有新生中有一些是假扮的小学妹，为了知道那些是真正的小学妹，组长想到了一个好办法：
已知n个整数b1,b2,…,bn,他们分别代表所有的新生,以及一个整数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。

Input

第一行两个整数：n , k 。（1<=n<=20，k＜n）
第二行n个整数：x1,x2，…,xn 。（1<=xi<=5000000）

Output

一个整数（满足条件的方案数）。

Sample Input 1

4 3
3 7 12 19

Sample Output 1

1

思路：

由于N和K都是不确定的，所以我们没法写出具体多少个循环来算，只能用递归。每递归一次，参数K就减小1，当K等于0时，判断sum的值是否为素数，是的话答案加1。思路其实就是这样，看起来简单，但理清并写出来确实有点难，但我相信聪明的你看完我的源码后能自己写出来。

源码：

#include<iostream>
#include<math.h>
#include<stdlib.h>
using namespace std;
int count=0;//输出的答案
//判断n是否是素数，应该都写过很多次了，就不解释了
int judge(int n){
    int m=sqrt(n);
    for(int i=2;i<=m;i++){
        if(n%i==0){
            return 0;//否
        }
    }
    return 1;//是
}
//递归体，使用了DFS的思路
void opera(int *num,int n/*总数*/,int k/*取K个数*/,int sum/*所求和*/,int s/*开始处*/){
    if(k==0){//即已经取出了k个数并求和
        if(judge(sum)){
            count++;
            return ;
        }
    }
    else{
        int i;
        for(i=s;i<n;++i){//从开始依次处取数
            opera(num,n,k-1,sum+num[i],i+1);
        }
    }
}
//主函数
int main(){
    int n,k;
    cin>>n>>k;
    int num[n];
    for(int i=0;i<n;i++){
        cin>>num[i];
    }
    opera(num,n,k,0,0);
    cout<<count<<endl;
    return 0;
}