1 条题解

  • 0
    @ 2022-11-5 16:55:56

    深搜

    #include<bits/stdc++.h>
    using namespace std;
    int n;
    int a[25];
    int ans;
    bool is_prime(int x)
    {
        if (x < 2)
            return false;
        for (int i = 2; i * i <= x; i++)
            if (x % i == 0)
                return false;
        return true;
    }
    
    //当前考虑第step个数选不选,之前选择的总和为sum 
    void dfs(int step,int sum){
    	if(step==n+1){
    		//现在得到了一种方案,总和是sum
    		if(is_prime(sum))
    			ans++;
    		return;
    	}
    	//选第step个数
    	dfs(step+1,sum+a[step]); 
    	//不选第step个数 
    	dfs(step+1,sum);
    }
    int main()
    {
    	cin>>n;
    	for(int i=1;i<=n;i++)
    		cin>>a[i];
    	ans=0;
    	dfs(1,0);
    	cout<<ans<<"\n";
    	return 0;
    }
    

    位运算

    #include<bits/stdc++.h>
    using namespace std;
    int n;
    int a[25];
    
    bool p(int 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;
    	for(int i=0;i<n;i++)
    		cin>>a[i];
    		
    	int ans=0;
    	for(int now = 0;now < (1 << n); now++){
    		//计算出来这种方案选择的数的和  
    		int sum = 0;
    		for(int i=0;i<n;i++){
    			//看一下 now 的 2^i 位是否为 1  
    			//即表示了是否选择了 a[i]
    			if(now & (1<<i))
    				sum+=a[i]; 
    		}
    		if(p(sum))
    			ans++;
    	}
    	
    	cout<<ans<<"\n";
    	return 0;
    }
    
    • 1

    信息

    ID
    1134
    时间
    1000ms
    内存
    256MiB
    难度
    3
    标签
    递交数
    79
    已通过
    42
    上传者