# include <bits/stdc++.h>
using namespace std;
int n, k;
long long ans;
int a[25], b[25];
bool isprime(int n) {
	if (n <= 1) {
		return 0;
	}
	for (int i = 2; i * i < n; i++) {
		if (n % i == 0) {
			return 0;
		}
	}
	return 1;
}
void dfs(int now, int cnt) {
	if (now > n) {
		if (cnt == k) {
			int sum = 0;
			for (int i = 0; i < k; i++) {
				sum += b[i];
			}
			if (isprime(sum)) {
				ans++;
			}
		}
		return;
	}
	b[cnt] = a[now];
	dfs(now + 1, cnt + 1);
	dfs(now + 1, cnt);
}
int main() {
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
	}
	dfs(1, 0);
	printf("%lld", ans);
	return 0;
} 

深度优先搜索(DFS)+回溯

代码如下

#include <bits/stdc++.h>
using namespace std;
int n,k,a[25],sum,ans;
bool f[25];//标记哪些数字已被选中

//判断整数x是否是质数的函数
bool prime(int x)
{
  if(x==1) return false;//特殊处理x=1
  for(int i=2; i*i<=x; i++)
  {
    if(x%i==0) return false;
  }
  return true;
}
/*深度优先搜索(DFS)函数
  x：已经选了x个数
  start：从a数组下标为start的那个数开始选数*/
void dfs(int x,int start)
{
  for(int i=start; i<=n; i++)
  {
    if(f[i]==false)//如果未被选中，那么就加上该数a[i]
    {
      sum+=a[i];
      f[i]=true;//标记a[i]的下标
      if(x==k)//如果已有k个数，判断是否为素数，如果是，ans+1
      {
        if(prime(sum)==true)
        {
          ans++;
        }
      }
      else dfs(x+1,i);//如果还没有k个数，递归 
      // 回溯，把之前添加的数从和中减去，并标记下标为未选中
      sum-=a[i];
      f[i]=false;
    }
  }
}


int main()
{
  scanf("%d%d",&n,&k);
  for(int i=1; i<=n; i++) scanf("%d",&a[i]);
  // 搜索第1个数，从数组a的第1个数开始
  dfs(1,1);
  printf("%d",ans);
  return 0;
}