P1036 [NOIP 2002 普及组] 选数

#include <bits/stdc++.h>
using namespace std;

int n, k;
int a[25];
int ans = 0;

// 判断 x 是否为素数：试除到 sqrt(x) 为止
bool isPrime(int x) {
    if (x < 2) return false;
    if (x == 2) return true;
    if (x % 2 == 0) return false;
    for (int d = 3; 1LL * d * d <= x; d += 2) {
        if (x % d == 0) return false;
    }
    return true;
}

// 从下标 start 开始再选 need 个数，当前已选出的和是 sum
void dfs(int start, int need, int sum) {
    if (need == 0) {                 // 已经选满 k 个，检查它们的和是不是素数
        if (isPrime(sum)) ans++;
        return;
    }
    for (int i = start; i <= n - need; i++) {
        dfs(i + 1, need - 1, sum + a[i]);
    }
}

int main() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> a[i];
    dfs(0, k, 0);
    cout << ans << "\n";
    return 0;
}