记录编号	397281	评测结果	AAAAA
题目名称	[NOIP 2002]选数	最终得分	100
用户昵称	ユッキー	是否通过	通过
代码语言	C++	运行时间	0.001 s
提交时间	2017-04-19 21:47:25	内存使用	0.31 MiB

#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;
int n,k;
int a[22];
int cnt=0;
bool pd(int num)
{
    if(num==2)return true;
    int i;
    int x=sqrt(num);
    for(i=2;i<=x;i++)
    {
        if(num%i==0)
            return false;
    }
    return true;
}
void dfs(int t,int s,int all)
{
    int i;
    if(s==k+1)
    {
        if(pd(all))
            cnt++;
        return;
    }
    for(i=t;i<=n;i++)
    {
        all+=a[i];
        dfs(i+1,s+1,all);
        all-=a[i];
    }
}
int main()
{
    int i;
    freopen("choose.in","r",stdin);
    freopen("choose.out","w",stdout);
    scanf("%d%d",&n,&k);
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
    dfs(1,1,0);
    printf("%d",cnt);
    return 0;
}