思路

• 先用线性筛得到所有可能用到的素质，再用DFS判断不同组合之和是否为素数。

代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int s = 5 * (int)1e6;
vector<int> p;
bool np[s];
int n, k;
bool isVisited[20];
int num[20];
int ans;
int sum;
void pre()
{
    for (int i = 2; i <= s; i++)
    {
        if (!np[i])
        {
            p.push_back(i);
        }
        for (auto it : p)
        {
            if (i * it > s)
            {
                break;
            }
            np[i * it] = true;
            if (i % it == 0)
            {
                break;
            }
        }
    }
}
void dfs(int t, int s)
{
    if (t == k)
    {
        if (find(p.begin(), p.end(), sum) != p.end())
        {
            ans++;
        }
        return;
    }
    for (int i = s; i < n; i++)
    {
        if (!isVisited[i])
        {
            sum += num[i];
            isVisited[i] = true;
            dfs(t + 1, i + 1);
            sum -= num[i];
            isVisited[i] = false;
        }
    }
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    pre();
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        cin >> num[i];
    }
    dfs(0,0);
    cout << ans;
    return 0;
}