问题标题: 酷町堂：暑假问答第十四天

5013 RE 10分

#include<bits/stdc++.h>
using namespace std;
int n,k,a[25],ans;
bool b[5000005];
void dfs(int x,int front,long long s){
	if(x==k){
		//cout<<s<<"\n";
		if(b[s]==0)
			ans++;
		return ;
	}
	for(int i=front+1;i<=n;i++){
		dfs(x+1,i,s+a[i]);
	}
}
int main(){
	cin>>n>>k;
	b[1]=1;
	for(int i=2;i<=5000000;i++)if(b[i]==0)for(int j=i*2;j<=5000000;j+=i)b[j]=1;
	for(int i=1;i<=n;i++)cin>>a[i];
	dfs(0,0,0);
	cout<<ans;
    return 0;
}

威慑么？？？

包涵宇在2020-07-22 15:10:52追加了内容

看了一下，是数组大小小了，超时0分（代码无问题，如何解决埃氏筛超时？）

#include<bits/stdc++.h>
using namespace std;
int n,k,a[25],ans;
bool b[100000005];
void dfs(int x,int front,long long s){
    if(x==k){
        //cout<<s<<"\n";
        if(b[s]==0)
            ans++;
        return ;
    }
    for(int i=front+1;i<=n;i++){
        dfs(x+1,i,s+a[i]);
    }
}
int main(){
    cin>>n>>k;
    b[1]=1;
    for(int i=2;i<=100000000;i++)if(b[i]==0)for(int j=i*2;j<=100000000;j+=i)b[j]=1;
    for(int i=1;i<=n;i++)cin>>a[i];
    dfs(0,0,0);
    cout<<ans;
    return 0;
}