这道题需要通过dfs去遍历三个不同元素的组合，最后再用单个的普通筛法筛取素数。

下面解释一下dfs搜索的方法。

一个最多20个数，每一次循环为1或0的循环，即表示这个数是否被选择。

搜索停止的条件就是元素满足三个的时候，即return; 。

然后循环次数达到元素个数的时候也停止搜索。

筛法就是普通筛法，数据组数很少。

AC代码

#include <bits/stdc++.h>
using namespace std;
int n, k, q = 0;
long long a[100], sum[100], num = 0, Sum = 0, judge = 1, jie = 1;
void dfs(int now)
{
    if (num == k)
    {
        sum[q++] = Sum;
        return;
    }
    if (now == n)
    {
        return;
    }
    for (int i = 1; i >= 0; i--)
    {
        if(i)
        {
            Sum += a[now];
            num++;
            dfs(now + 1);
            Sum -= a[now];
            num--;
        }
        else
        {
            dfs(now + 1);
        }
    }
}
bool isprime(long long x)
{
    for (long long i = 2; i <= sqrt(x); i++)
    {
        if (x % i == 0)
        {
            return false;
        }
    }
    return true;
}
int main()
{
    cin >> n >> k;
    int temp = n, temp2 = k, ans = 0;
    for(int i = 0;i < k;i++)
    {
        judge *= temp--;
        jie *= temp2--;
    }
    judge /= jie;
    memset(a, 0, sizeof(a));
    memset(sum, 0, sizeof(sum));
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    dfs(0);
    for (int i = 0; i < q; i++)
    {
        if (isprime(sum[i]))
        {
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

这道题我是用枚举的方法做的。

用二进制的每一位代表这个数选不选。

如果1的数量与k不等就跳过。

否则累加，计算

AC CODE:

#include <bits/stdc++.h>
using namespace std;
int n , k , ans , x[25];
bool is_prime(int x)//判断质数
{
    for (int i = 2 ; i * i <= x ; i++)
    {
        if (x % i == 0) return false;
    }
    return true;
}

int main()
{
    cin >> n >> k;
    for (int i = 1 ; i <= n ; i++) cin >> x[i];

    for (int i = 1 ; i <= (1 << n) ; i++)
    {
        if (__builtin_popcount(i)/*返回i二进制下1的数量*/ != k) continue;
        int sum = 0;
        for (int j = 0 ; j <= n ; j++)
        {
            if (i & (1 << j))//与运算
            {
                sum += x[j + 1];
            }
        }
        if (is_prime(sum)) ans++;
    }
    cout << ans;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n,k;
int a[25];
long long ans;
bool prime(int x){
	for (int i=2;i*i<=x;i++){ //也可以用sqrt(x)<=x 
		if (x%i==0){
			return false;
		}
	}
	return true;
}//判断质数 
void dfs(int m,int sum,int sx){
	if (m==k){//全部选完 
		if (prime(sum)){
			ans++;
		}//和是不是质数  是就ans加一 
		return ;
	}
	for (int i=sx;i<n;i++){
		dfs(m+1,sum+a[i],i+1);//递归 m+1也就是选了一个数，总和当然要加 
	}
	return ;
}
int main(){
	cin>>n>>k;
	for (int i=0;i<n;i++){
		cin>>a[i];
	}
	dfs(0,0,0);//调用 
	cout<<ans;//输出 
	return 0;
}

去重可以不在dfs里写出来，最后直接除k!就行了

#include<bits/stdc++.h>
using namespace std;
int n,k,x[27],xxx;
bool book[27];
bool is_prime(int xx)
{
    for (int i=2;i*i<=xx;i++)
        if (xx%i==0)
            return 0;
    return 1;
}
int qwq(int xxxx)
{
    if (xxxx==1)
        return 1;
    return xxxx*qwq(xxxx-1);
}
void awa(int d,int ans)
{
    if (d==k+1)
        if (is_prime(ans))
            xxx++;
    for (int i=1;i<=n;i++)
        if (!book[i])
        {
            book[i]=1;
            awa(d+1,ans+x[i]);
            book[i]=0;
        }
}
int main()
{
    cin>>n>>k;
    for (int i=1;i<=n;i++)
        cin>>x[i];
    awa(1,0);
    cout<<xxx/qwq(k);
    return 0;
}

指数型枚举的模板题，每个数字选和不选，进行dfs，选的同时求和，最后选到最后一个，看一下总和是不是质数。