题目链接：https://www.luogu.org/problemnew/show/1036
题目描述：
已知 n 个整数 x1,x2,…,xn，以及一个整数 k（k＜n）。从 n 个整数中任选 k 个整数相加，可分别得到一系列的和。例如当 n=4，k＝3，4 个整数分别为 3，7，12，19 时，可得全部的组合与它们的和为：
3＋7＋12=22
3＋7＋19＝29
7＋12＋19＝38
3＋12＋19＝34。
现在，要求你计算出和为素数共有多少种。(n <=20)
分析:因为n <= 20, 所以暴力即可。
#pragma GCC optimize(3) #include<bits/stdc++.h> #define mst(a,b) memset(a,b,sizeof(a)) #define For(i, k, j) for(int i = (k); i <= (j); i++) #define INF 2147483647/3 #define ll long long using namespace std; inline int read() { int num = 0, flag = 1; char c=' '; for(;c>'9'||c<'0';c=getchar()) if(c=='-') flag = -1; for(;c>='0'&&c<='9';num=(num<<1)+(num<<3)+c-48,c=getchar()); return num * flag; } #define N 25 int a[N]; bool p[N]; int n, k; int ans = 0; inline bool isprime(int a) {//质数判断 if(a == 1) return 0; if(a == 2 || a == 3) return 1; if(a%6 != 1 && a%6 != 5) return 0; int g = sqrt(a); for(int i = 5; i <= g; i += 6) { if(!(a%i)|| !(a%(i+2))) return 0; } return 1; } void dfs(int s) {//暴力搜索 if(s == n + 1) { int sum = 0; For(i, 1, n) { if(p[i]) sum++; } if(sum == k) { sum = 0; For(i, 1, n) { if(p[i]) sum += a[i]; } if(isprime(sum)) { ans++; } } return; } p[s] = 1; dfs(s + 1); p[s] = 0; dfs(s + 1); } int main() { n = read(), k = read(); For(i, 1, n) { scanf("%d", &a[i]); } dfs(1); printf("%d\n", ans); return 0; }说实话，我已经快一个月没有打深搜了，居然还可以一遍过。
