线上OJ：
一本通：1919：【02NOIP普及组】选数 (opens in a new tab)
AcWing：5491. 选数 (opens in a new tab)
洛谷：P1036 [NOIP2002 普及组] 选数 (opens in a new tab)
核心思想：
1、使用 模板函数 isPrime() 来判断一个数是否为素数。
2、定义一个函数 dfs 来进行深度优先搜索。在dfs函数中，通过递归的方式遍历所有可能的组合，并计算每个组合的和。
如果坐标 id 超过n，则越界，返回。
如果已选了k个数，且和为素数，则 ans 加 1。
否则，就对剩余的 [id+1, n] 个数进行枚举深搜
判断素数的模板函数
bool isPrime(int a)
{
if(a < 2) return false;
for(int i = 2; i * i <= a; i++)
if(a % i == 0) return false;
return true;
}题解代码：
dfs深搜
#include <bits/stdc++.h>
using namespace std;
int n, k, ans;
int x[25];
// 判断一个数是否为素数
bool isPrime(int a)
{
if(a < 2) return false;
for(int i = 2; i * i <= a; i++)
if(a % i == 0) return false;
return true;
}
// (当前已选数的和，当前数的索引，已经选了几个数)
void dfs(int sum, int id, int cnt)
{
if (id > n) return; // 如果传进来的数的索引已经超过了 n ，则越界，返回
else if (k == cnt && isPrime(sum)) // 否则，如果当前传进来已选的数已达到k个，且此时k个数的总和是素数
ans++;
else // 否则，继续向下深搜（此时，要枚举后续每一个元素）
{
for (int i = id + 1; i <= n; i++)
dfs(sum + x[i], i, cnt + 1);
}
}
int main()
{
scanf("%d %d", &n, &k);
for (int i = 1; i <= n; i++) cin >> x[i]; // 存储的索引为 1~n
ans = 0;
dfs(0, 0, 0); // (当前已选数的和，当前数的索引，已经选了几个数)
printf("%d\n", ans);
return 0;
}