记录编号	100822	评测结果	AAAAA
题目名称	[NOIP 2002]选数	最终得分	100
用户昵称	OI永别	是否通过	通过
代码语言	C++	运行时间	0.008 s
提交时间	2014-05-08 07:19:05	内存使用	0.77 MiB

#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
#define N 101000
bool f[N];
int p[N];

void get_prime(){
	f[1] = f[0] = 1;
	for (int i = 2; i <= N; i ++){
		if (f[i]) continue;
		p[++p[0]] = i;
		for (int j = i; j <= N / i; j ++){
			f[i * j] = 1;
		}
	}
	return;
}

bool isprime(int x){
	if (x < N) return !f[x];
	for (int i = 1; p[i] >= (int)sqrt(x) , i <= p[0]; i ++){
		if (x % p[i] == 0) return 0;
	}
	return 1;
}
int n,k;
int a[35];
int main(){
	freopen("choose.in","r",stdin);
	freopen("choose.out","w",stdout);
	get_prime();
	scanf("%d%d",&n,&k);
	int ans = 0;
	for (int i = 1; i <= n; i++) scanf("%d",&a[i]);
	for (int i = 0; i < (1 << n) ; i ++){
		int choose = 0,sum = 0;
		for (int j = 0; j < n; j ++){
			if ((1 << j) & i) sum += a[j + 1],choose ++;
		}
		if (choose == k && isprime(sum)) ans ++;
	}
	printf("%d\n",ans);
	return 0;
}