P-1036-选数（从n个数选出k个,求这k个数和为素数的方案数）

题目

输入样例#1：

4 3
3 7 12 19

输出样例#1：

1

#include <cstdio>
#include <cmath>
#define sd(a) scanf("%d",&a)
using namespace std;
const int N=20+5;
int n,K,val[N];
int isprime(int x)
{
    int flag=0;
    for(int i=2;i<=sqrt(x);i++)
    {
        if(!(x%i))
        {
            flag=1;
            break;
        }
    }
    return flag^1;
}
int dfs(int pos,int k,int ans)  //选到第pos个位置,已经选了k个数的和为ans；
{
    if(pos==n+1||k==K)       //把数组遍历完或者已经选了k个数
    {
        if(k==K&&isprime(ans))  //k==K,且选好的数的和是prime。
             return 1;
        return 0;
    }
    return dfs(pos+1,k+1,ans+val[pos])+dfs(pos+1,k,ans);
}
int main()
{
    scanf("%d%d",&n,&K);
    for(int i=1;i<=n;i++)
        sd(val[i]);
    printf("%d\n",dfs(1,0,0)); //从第一个位置开始,已选0个数和为0.
}