11.3 晚19:36预言：今天必讲这个题 预言失败了

组合质数

从一堆数字里面选择几个数（不重复），加和为质数。很容易想到的思路是从第一个数字开始深搜查找，如果是质数就总数加一。

需要解决的分为两部分：深搜&质数判断 质数判断：因为每个数都小于50000，所以基本的质数判断方法直接运行也不会超时。 深搜：很标准，很模板。需要注意的是这个和其他的走迷宫题不同，需要在已经确定当前和为质数之后继续搜索，因为再加一个数字有可能还是质数。

蒟蒻声明：

本篇题解所使用的方法不是也不可能是最优解，一切标准答案参考33dai的代码，如有不同之处请忽略本人代码并且无需理解，因为一定是我错了。

标准的深搜题，当然我这个方法或许时间复杂度有点高，代老师的代码极有可能跑出更快速、更高效，所以理解一下思路就好了。

上代码

#include<bits/stdc++.h>
using namespace std;
int n,a[30],num;
bool zhishu(int x)   //质数判断 
{
	if(x==0||x==1) return false;   //特判一下0、1均不是质数 
	for(int i1=2;i1*i1<=x;i1++)  //很低效但也比较易于理解的质数判断 
		if(x%i1==0)  //即从2~根号n循环求余，如果有余数为0则可以整除 
			return false;  //返回假 
	return true; //否则就是质数，返回真 
}
void dfs(int m,int sum)   //深搜主体 
{
	if(zhishu(sum)==true) num++;
	//如果当前的数字之和为质数，总数加一 
	for(int i=m;i<=n;i++)
	{
		sum+=a[i];  //加和 
		dfs(i+1,sum);  //深搜下一层 
		sum-=a[i];  //减去当前数（回溯，便于下一重循环继续判断） 
	}
	return;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];  //输入数据 
	dfs(1,0);  //深搜 
	cout<<num;  //输出结果 
	return 0;
}

深搜

#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;
}