[NOIP2002 普及组] 选数

#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;
}