记录编号	27848	评测结果	AAAAA
题目名称	50.[NOIP 2002]选数	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	0.001 s
提交时间	2011-10-08 21:33:49	内存使用	0.27 MiB

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int sum=0;//當前總和
int num[21];
int n,k;
int tot=0;

bool prime(int num)
{
	if (num==1)return false;
	for (int i=2;i<=(int)sqrt(double(num));i++)
		if (num%i==0)
			return false;
	return true;	
}


void dg(int dep,int loc)
{
	if(k-dep>n-loc) return;
	if (dep==k+1)
	{
		if (prime(sum))
			tot++;
	}
	if (dep<k+1)
	{
		for (int i=loc;i<=n;i++)
		{
			sum+=num[i];
			dg(dep+1,i+1);
			sum-=num[i];
		}
	}
}

int main()
{
	freopen("choose.in","r",stdin);
	freopen("choose.out","w",stdout);
	cin>>n>>k;
	for (int i=1;i<=n;i++)
		cin>>num[i];
	dg(1,1);
	cout<<tot<<endl;
	return 0;
}