[NOIP2002 普及组] 选数
2025年2月26日小于 1 分钟
#include <bits/stdc++.h>
using namespace std;
int n, k;
int x[25];
// 判断质数
bool isP(int x)
{
if (x < 2)
return false;
for (int i = 2; i * i <= x; i++)
if (x % i == 0)
return false;
return true;
}
// dfs
int ans;
void dfs(int pos, int cnt, int sum)
{
if (cnt == k)
{
if (isP(sum))
ans++;
return;
}
if (pos == n + 1)
return;
dfs(pos + 1, cnt + 1, sum + x[pos]);
dfs(pos + 1, cnt, sum);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> k;
for (int i = 1; i <= n; i++)
cin >> x[i];
ans = 0;
dfs(1, 0, 0);
cout << ans;
return 0;
}