73 lines
2.0 KiB
C++
73 lines
2.0 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
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;
|
||
} |