求助一下关于素数环等于20的时候解的个数
  • 板块学术版
  • 楼主Shikieiki
  • 当前回复2
  • 已保存回复2
  • 发布时间2020/10/19 20:43
  • 上次更新2023/11/5 10:22:41
查看原帖
求助一下关于素数环等于20的时候解的个数
152860
Shikieiki楼主2020/10/19 20:43

如题,我的素数环已经跑了好久了,还没跳出运行,想请问当等于20的时候解的个数,以及优化的建议,感谢

#include <iostream>
#include <cmath>
using namespace std;
int a[25];//答案存储位 
bool b[25];
int ans; 
int su(int a,int b);
void print();
int dfs(int k){
	for(int i=1;i<=20;i++){
		if(b[i]==0&&su(i,a[k-1])){//当确定这个数字没有被用过且和上一位是素数的时候 
			a[k]=i;//把第k位设置成i
			b[i]=1;//标记这个数字用过了,不然下次会重复
			if(k==20){ //判断是不是结尾
				if(su(a[k],a[1])){ //当判断结尾和开头为素数的时候 
					print(); //输出 
				} 
			} 
				else
				{        //当判断这个数字不满足没有被用过或和上一位不是素数时 
					dfs(k+1);//换新的 
				}
			b[i]=0;
		}
		
	}
}
int su(int a,int b){
	int p=0;    //设置一个p=a+b 
	bool flag=1;//设置一个标记记号,标记是否为素数 
	p=a+b;     //没用 
	for(int i=2;i<=sqrt(p);i++){  //循环增加除数i 
		if(p%i==0){         //当被除数p和i取余后,如果等于零了就证明可以被整除(也就是不是素数) 
			flag=0;         //将flag设置成零,为后续做准备
			return flag;    //因为只要判断一个是可以被整除,就可以证明非素数,所以直接返回假值 
		}
	}
	return flag;            //当如果一个是素数判定成功后,返回真值 
} 
void print(){
	ans++;
	cout<<ans<<":";
	for(int i=1;i<=20;i++){
		cout<<a[i]<<" "; 
	}
	cout<<endl;
}
int main(){
	int e=0;
	//cin>>e;
	dfs(1);
	return 0;
}
2020/10/19 20:43
加载中...