dfs
by InversionShadow @ 2024-01-28 07:25:12
看标签啊，不都写了深度优先搜索
by houwz351 @ 2024-01-28 08:22:29
@[a13901280570](/user/1070752) 哈哈，这道题经我尝试，有问题，在数据上 $1\le k\le 10$ 。所以附上我的代码：
```C++
#include<bits/stdc++.h>
using namespace std;
long long n,k,a[25],ans;
bool is_prime(long long x) {
if(x<2) {
return false;
}
for(int i=2;i*i<=x;i++) {
if(x%i==0) {
return false;
}
}
return true;
}
int main() {
cin>>n>>k;
for(int i=1;i<=n;i++) {
cin>>a[i];
}
if(k==1) {
for(int i=1;i<=n;i++) {
if(is_prime(a[i])) {
ans++;
}
}
}
else if(k==2) {
for(int i=1;i<=n;i++) {
for(int j=i+1;j<=n;j++) {
if(is_prime(a[i]+a[j])) {
ans++;
}
}
}
}
else if(k==3) {
for(int i=1;i<=n;i++) {
for(int j=i+1;j<=n;j++) {
for(int k=j+1;k<=n;k++) {
if(is_prime(a[i]+a[j]+a[k])) {
ans++;
}
}
}
}
}
else if(k==4) {
for(int i=1;i<=n;i++) {
for(int j=i+1;j<=n;j++) {
for(int k=j+1;k<=n;k++) {
for(int b=k+1;b<=n;b++) {
if(is_prime(a[i]+a[j]+a[k]+a[b])) {
ans++;
}
}
}
}
}
}
else if(k==5) {
for(int i=1;i<=n;i++) {
for(int j=i+1;j<=n;j++) {
for(int k=j+1;k<=n;k++) {
for(int b=k+1;b<=n;b++) {
for(int c=b+1;c<=n;c++) {
if(is_prime(a[i]+a[j]+a[k]+a[b]+a[c])) {
ans++;
}
}
}
}
}
}
}
else if(k==6) {
for(int i=1;i<=n;i++) {
for(int j=i+1;j<=n;j++) {
for(int k=j+1;k<=n;k++) {
for(int b=k+1;b<=n;b++) {
for(int c=b+1;c<=n;c++) {
for(int d=c+1;d<=n;d++) {
if(is_prime(a[i]+a[j]+a[k]+a[b]+a[c]+a[d])) {
ans++;
}
}
}
}
}
}
}
}
else if(k==7) {
for(int i=1;i<=n;i++) {
for(int j=i+1;j<=n;j++) {
for(int k=j+1;k<=n;k++) {
for(int b=k+1;b<=n;b++) {
for(int c=b+1;c<=n;c++) {
for(int d=c+1;d<=n;d++) {
for(int e=d+1;e<=n;e++) {
if(is_prime(a[i]+a[j]+a[k]+a[b]+a[c]+a[d]+a[e])) {
ans++;
}
}
}
}
}
}
}
}
}
else if(k==8) {
for(int i=1;i<=n;i++) {
for(int j=i+1;j<=n;j++) {
for(int k=j+1;k<=n;k++) {
for(int b=k+1;b<=n;b++) {
for(int c=b+1;c<=n;c++) {
for(int d=c+1;d<=n;d++) {
for(int e=d+1;e<=n;e++) {
for(int f=e+1;f<=n;f++) {
if(is_prime(a[i]+a[j]+a[k]+a[b]+a[c]+a[d]+a[e]+a[f])) {
ans++;
}
}
}
}
}
}
}
}
}
}
else if(k==9) {
for(int i=1;i<=n;i++) {
for(int j=i+1;j<=n;j++) {
for(int k=j+1;k<=n;k++) {
for(int b=k+1;b<=n;b++) {
for(int c=b+1;c<=n;c++) {
for(int d=c+1;d<=n;d++) {
for(int e=d+1;e<=n;e++) {
for(int f=e+1;f<=n;f++) {
for(int g=f+1;g<=n;g++) {
if(is_prime(a[i]+a[j]+a[k]+a[b]+a[c]+a[d]+a[e]+a[f]+a[g])) {
ans++;
}
}
}
}
}
}
}
}
}
}
}
else if(k==10) {
for(int i=1;i<=n;i++) {
for(int j=i+1;j<=n;j++) {
for(int k=j+1;k<=n;k++) {
for(int b=k+1;b<=n;b++) {
for(int c=b+1;c<=n;c++) {
for(int d=c+1;d<=n;d++) {
for(int e=d+1;e<=n;e++) {
for(int f=e+1;f<=n;f++) {
for(int g=f+1;g<=n;g++) {
for(int h=g+1;h<=n;h++) {
if(is_prime(a[i]+a[j]+a[k]+a[b]+a[c]+a[d]+a[e]+a[f]+a[g]+a[h])) {
ans++;
}
}
}
}
}
}
}
}
}
}
}
}
else if(k==11) {
}
else if(k==12) {
}
else if(k==13) {
}
else if(k==14) {
}
else if(k==15) {
}
else if(k==16) {
}
else if(k==17) {
}
else if(k==18) {
}
else if(k==19) {
}
else if(k==20) {
}
cout<<ans;
return 0;
}
```
by daiyulong2024 @ 2024-01-29 18:56:37
@[a13901280570](/user/1070752) 因为你想想，这道题目的难度才 普及- ，$k> 10$ 时都超时了，所以数据范围是吓唬人的。
by daiyulong2024 @ 2024-01-29 18:58:15
@[daiyulong2024](/user/1272852) 暴力大佬
by FIGFUH001 @ 2024-02-02 08:34:15
@[a13901280570](/user/1070752) 好像阔以，但是需要用排列组合
by Jadejunxi @ 2024-02-13 21:07:24
@[a13901280570](/user/1070752) 还有[埃拉托斯特尼筛法](https://oi-wiki.org/math/number-theory/sieve/#%E5%9F%83%E6%8B%89%E6%89%98%E6%96%AF%E7%89%B9%E5%B0%BC%E7%AD%9B%E6%B3%95)
by Jadejunxi @ 2024-02-13 21:12:15
埃式筛或者欧拉筛
by Jadejunxi @ 2024-02-13 21:16:23