一：题目分析：

题目描述

已知 n个整数 x1,x2,??,xn以及 1 个整数 k（k<n）。从 n 个整数中任选 k个整数相加，可分别得到一系列的和。例如当 n=4，k=3，4 个整数分别为 3,7,12,193时，可得全部的组合与它们的和为：

3+7+12=22 (应该是要进行搜索)

3+7+19=29

7+12+19=38

3+12+19=34

现在，要求你计算出和为素数共有多少种。（还要判断素数）

例如上例，只有一种的和为素数：3+7+19=29。

输入格式

第一行两个空格隔开的整数 n,k（1≤n≤20，k<n）。

第二行 n 个整数，分别为 x1,x2,??,xn（1≤xi?≤5×10^6) （int型就可以了）

输出格式

输出一个整数，表示种类数。

二：解题

1.判断质数的函数：

这里用最暴力的方法：（如果你牛逼可以用别的，质数筛等等）

int sushu(int x)//判断质数的函数
{if (x == 2 || x == 3 || x == 5)return 1;if (x < 2 || x % 2 == 0)return 0;for (int i = 3; i < sqrt(x); i += 2)//每次加2提高效率，虽然复杂度一样^_^if (x % i == 0)return 0;return 1;
}

2.深度优先算法求解组合数目：

首先要创建数组来存储数据和作为标记数组（定义的是全局变量更方便一点）

int count;//记录组合的个数
int arr[20];//存储数据
int book[20];//标记数组

然后就是实现函数：

void dfs1(int x, int num)//深度优先算出有几种可能，这个数量是答案乘以k个数全排列的个数
{if (x == 0)//如果到了k这么多层，这里的x就会等于0，然后进行质数判断{if (sushu(num))count++;return;//不管是不是质数到了k层都要退出}for (int i = 0; i < n; i++){if (book[i] == 0)//如果那个数没有用{book[i] = 1;//标记用了dfs1(x - 1, num + arr[i]);//进入下一层book[i] = 0;//出来以后一定要记得把标记变回来}}return;
}

3.求出k个数的全排列：

由上面可知dfs1算出来的是答案个数乘以k的全排列，因为这样算的话只要加数的位置交换就又算作一种情况：

所以要求出k个数的全排列：

void dfs2(int x)//求出k个数的全排列的个数
{if (x == 0)//结束递归条件{num++;return;}for (int i = 0; i < k; i++){if (book2[i] == 0)//如果没有用{book2[i] = 1;//标记已用dfs2(x - 1);book2[i] = 0;//标记还原}}return;
}

最后count/=num就是最终答案。

三：完整代码

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<math.h>
int count;
int num;
int arr[20];
int book[20];//标记数组
int book2[20];//标记数组
int n, k;
int sushu(int x)//判断质数的函数
{if (x == 2 || x == 3 || x == 5)return 1;if (x < 2 || x % 2 == 0)return 0;for (int i = 3; i < sqrt(x); i += 2)if (x % i == 0)return 0;return 1;
}
void dfs1(int k, int num)//深度优先算出有几种可能，这个数量是答案乘以k个数全排列的个数
{if (k == 0){if (sushu(num))count++;return;}for (int i = 0; i < n; i++){if (book[i] == 0)//如果没有用{book[i] = 1;//标记用了dfs1(k - 1, num + arr[i]);//进入下一层book[i] = 0;//出来以后一定要记得把标记变回来}}return;
}
void dfs2(int x)//求出k个数的全排列的个数
{if (x == 0)//结束递归条件{num++;return;}for (int i = 0; i < k; i++){if (book2[i] == 0)//如果没有用{book2[i] = 1;//标记已用dfs2(x - 1);book2[i] = 0;//标记还原}}return;
}
int main()
{scanf("%d%d", &n, &k);for (int i = 0; i < n; i++)scanf("%d", arr + i);dfs1(k, 0);dfs2(k);count /= num;printf("%d", count);
}