40 lines
687 B
C++
40 lines
687 B
C++
#include <iostream>
|
|
#include <vector>
|
|
using namespace std;
|
|
|
|
int js = 0;
|
|
vector<int> arr;
|
|
|
|
bool checkprime(int x) {
|
|
if (x < 2) return false;
|
|
for (int i = 2; i * i <= x; i++) {
|
|
if (x % i == 0) return false;
|
|
}
|
|
return true;
|
|
}
|
|
|
|
void dfs(int idx, int k, int sum) {
|
|
if (k == 0) { // 已经选了k个
|
|
if (checkprime(sum)) js++;
|
|
return;
|
|
}
|
|
if (idx >= arr.size()) return;
|
|
|
|
// 选择当前数
|
|
dfs(idx + 1, k - 1, sum + arr[idx]);
|
|
// 不选当前数
|
|
dfs(idx + 1, k, sum);
|
|
}
|
|
|
|
int main() {
|
|
int n, k;
|
|
cin >> n >> k;
|
|
arr.resize(n);
|
|
for (int i = 0; i < n; i++) cin >> arr[i];
|
|
|
|
dfs(0, k, 0);
|
|
cout << js << endl;
|
|
return 0;
|
|
}
|
|
|