#include using namespace std; /* 这个register int中的register 表示使用cpu内部寄存器(寄存器是中央处理器内的组成部分。寄存器是有限存贮容量的高速存贮部件)的变量, 而平时的int是把变量放在内存中,存到寄存器中可以加快变量的读写速度 这是一个循环1e8的代码在使用int的用时 注意一般在多层循环用 */ /** * 功能:判断是不是素数 * 作者:黄海 * 时间:2019-11-27 * @param x * @return * 注意:inline 内联函数 参考:http://c.biancheng.net/view/199.html */ inline bool prime(int x) { for (register int i = 2; i <= sqrt(x); i++) if (x % i == 0) return false; return true; } int a[10001]; //可以用一个a数组来记录我们所选的数 int n; // n是所有整数的个数 int k; // k是选择整数的个数 int total; //total为总方案数 /** * 功能:深度优先搜索的主函数 * 作者:黄海 * 时间:2019-11-27 * @param step :记录当前选的是第几个数 * @param sum :相加的和是什么 * @param cnt :已选的可用的数 */ inline void dfs(int step, int sum, int cnt) { //如果已经进行到了n+1次,或者是已经选了k个数 if (step == n + 1 || cnt == k) { //如果sum为一个素数且已经选了k个数 if (prime(sum) && cnt == k) { total++; //总方案数+1 } return; } //继续枚举不选择下一个数的情况 dfs(step + 1, sum, cnt); //继续搜索,选择下一个数 dfs(step + 1, sum + a[step], cnt + 1); return; } int main() { //读入输出优化的强迫症 ios::sync_with_stdio(false); //输入n和k cin >> n >> k; //输入数据 for (register int i = 1; i <= n; i++) { cin >> a[i]; } //从第1个数开始搜 dfs(1, 0, 0); //输出结果 cout << total; return 0; }