题目分析

本题为搜索题。

对于每个 $a_i$，都有取与不取两种情况。若取，则累加和，否则，保持原总和不变。最后，所有数字全部选好取与不取，即递归层数 $>n$ 时，判断总和是否为素数即可。

参考代码（C++）

#include<bits/stdc++.h>
using namespace std;
int n,k,ans;
int a[25];
void dfs(int d,int s,int sum){
    if(d>n){
        for(int i = 2;i*i<=sum;i++)if(!(sum%i))return;
        ans++;
        return;
    }
    if(s)dfs(d+1,s-1,sum+a[d]);
    if(n-d>=s)dfs(d+1,s,sum);
}
int main(){
    cin>>n>>k;
    for(int i = 1;i<=n;i++)cin>>a[i];
    dfs(1,k,0);
    cout<<ans;
}