题解

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

bool isPrime(int num) {
    if (num <= 1) {
        return false;
    }
    for (int i = 2; i <= sqrt(num); ++i) {
        if (num % i == 0) {
            return false;
        }
    }
    return true;
}

int cps(vector<int>& nums, int k, int currentIdx, int currentSum) {
    if (k == 0) {
        return isPrime(currentSum) ? 1 : 0;
    }
    
    int count = 0;
    for (int i = currentIdx; i < nums.size(); ++i) {
        count += cps(nums, k - 1, i + 1, currentSum + nums[i]);
    }
    
    return count;
}

int main() {
    int n, k;
    cin >> n >> k;
    
    vector<int> nums(n);
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }
    
    int result = cps(nums, k, 0, 0);
    cout << result << endl;
    
    return 0;
}