一、题目：
二、解题思路：
本文章采用的解决方法是递归与DFS(深度优先搜索)。
以下图是思路图：
1.首先-确定位置
题目说4个数字取三个数，所以考虑的只有三个位置和这三个位置分别放什么数值。从第一个位置开始放数。
2.其次-开始放数
分为4种可能，第一位置可以先放3，那么第二个位置就只能放7，12，19这三个数字任意一个数字了，假设放了7，那么第三个位置就只能放12或19。所以本次得到的结果是3 7 12或3 7 19.（这里只谈的简单思路，编写代码的或者写类似搜索题要注意回溯问题和恢复现场）。接着再继续列举其他可能性，得到最后结果为3 7 12，3 7 19，3 12 19，7 12 19这四种结果，发现与题目给的样例一致。
3.最后-考虑素数如何判断
素数是指只能被1和它自身整除的大于1的自然数。因此，判断一个数是否为素数，需要满足以下几个条件：
-
大于1的自然数：素数必须大于1，因为1不是素数。同时，它必须是自然数，即非负整数。
-
只有1和自身两个正因数：这是素数最核心的定义。也就是说，除了1和它本身以外，没有其他正整数能够整除它。如果一个数有除了1和它本身以外的其他正因数，那么它就不是素数。
素数（质数）的判断：检查该数是否能被比它小的任何正整数整除。如果能被整除，则它不是素数；如果不能被任何比它小的正整数整除，则它是素数。
步骤如下：
- 排除小于等于1的数：任何小于等于1的数都不是素数。
- 排除偶数：除了2以外，所有的偶数都不是素数，因为它们都可以被2整除。
- 检查奇数因子：从3开始，到被检测数的平方根为止，检查是否能被这些奇数整除。如果能被整除，则不是素数；如果不能被整除，则继续检查下一个奇数。
- 达到平方根即可停止：如果一个数有一个大于它平方根的因子，那么它必然还有一个小于或等于其平方根的因子。因此，我们只需要检查到被检测数的平方根即可。
三、分步骤-实现代码
1.先设置好全局变量
#include<iostream>
using namespace std;
const int N = 30;
int arr[N];//存答案
int q[N];//存数据
int n,k;
int res;//保存题目要求的种类数2.主函数
1）for循环用来给数组赋值
2）函数传参-当前枚举到哪个位置，从第一个位置开始
int main()
{
scanf("%d %d",&n,&k);
for(int i = 1; i <= n; i++)
{
scanf("%d",&q[i]);
}
dfs(1,1);
printf("%d\n",res);
return 0;
}3.开始遍历
利用for循环遍历
void dfs(int x, int start)//x表示当前到了哪个位置,start表示从几开始枚举
{
//选谁
for(int i = start; i <= n; i++){
arr[x] = q[i];
dfs(x + 1 , i + 1);//深度优先 继续向下
arr[x] = 0;//恢复现场
}
}遍历完所有数字以后开始求出总和，并进行判断是否为素数
if(x > k)
{
int sum = 0;
for(int i =1; i <= k; i++){
sum = sum + arr[i];
}
//prime number意思是素数
if(is_prime(sum)){
res++;
}
return ;
}
4.素数判断
bool is_prime(int sum){
if(sum < 2) return false;
for(int i = 2; i <= sum / i; i++){//如果写成i*i<=sum,数据大的时，可能会爆出int的最大范围,此处还可以写成i<=sqrt(sum)
if(sum%i==0)
{
return false;
}
}
return true;//此处有好几处判断以后才能返回true,易错点在if判断完以后用else return true.这样写就错了
}四、最终代码
#include<iostream>
using namespace std;
const int N = 30;
int arr[N];//存答案
int q[N];//存数据
int n,k;
int res;//保存题目要求的种类数
bool is_prime(int sum){
if(sum < 2) return false;
for(int i = 2; i <= sum / i; i++){//如果写成i*i<=sum,数据大的时，可能会爆出int的最大范围,此处还可以写成i<=sqrt(sum)
if(sum%i==0)
{
return false;
}
}
return true;//此处有好几处判断以后才能返回true,易错点在if判断完以后用else return true.这样写就错了
}
void dfs(int x, int start)//x表示当前到了哪个位置,start表示从几开始枚举
{
if(x > k)
{
int sum = 0;
for(int i =1; i <= k; i++){
sum = sum + arr[i];
}
//prime number意思是素数
if(is_prime(sum)){
res++;
}
return ;
}
//选谁
for(int i = start; i <= n; i++){
arr[x] = q[i];
dfs(x + 1 , i + 1);//深度优先 继续向下
arr[x] = 0;//恢复现场
}
}
int main()
{
scanf("%d %d",&n,&k);
for(int i = 1; i <= n; i++)
{
scanf("%d",&q[i]);
}
dfs(1,1);
printf("%d\n",res);
return 0;
}