洛谷P1036选数

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int a[1000], book[1000], m,n,sum,ans;
bool isprime(int x) {
	if (x == 0 || x == 1) return 0;
	else {
		for (int i = 2; i <= sqrt(x); i++)
			if (x % i == 0)
				return 0;
	}
	return 1;
}

void dfs(int x, int y) {
	for (int i = y; i <= m; i++) {
		if (book[i] == 0) {
			book[i] = 1;
			sum += a[i];
		}
		if (n == x) {
			if (isprime(sum)) ans++;
		}
		else
			dfs(x + 1, i + 1);
		sum -= a[i];
		book[i] = 0;
	}
}

int main() {
	
	cin >> m >> n;
	for (int i = 1; i <= m; i++)
		cin >> a[i];
	dfs(1, 1);
	printf("%d", ans);
	return 0;

}