素数环-dfs+素数打表

#include<stdio.h>
#include<string.h>
int a[50],b[50],vis[50],n;
void prime(){                  //素数打表 
	memset(a,0,sizeof(a));
	a[0]=a[1]=1;    //素数为0非素数为1
	for(int i =2;(!a[i])&&i<50;i++) //a[i]=1表明是素数，则其倍数也是素数因为i就是前边的素数的倍数
		for(int j=i+i;j<50;j+=i)
			a[j]=1;
}
bool dfs(int num){            
	for(int j=2;j<=num;j++){
		if(a[b[j-1]+b[j]]) return false;//如果相邻的两个相加不是素数就返回 
	}
	if(num==n){               //当个数够n个之后就查看最后一个和第一个相加是否是素数 
		if(!a[b[n]+b[1]]){
			return true;
		}
	} 
	for(int i=1;i<=n;i++){ 
		if(!vis[i]){
			b[num]=i;    //把b环中的第nnum个数复制成i  并标记使用过i 
			vis[i]=1;
			return dfs(num+1);
			vis[i]=0; 
		}
	}
} 
int main()
{
	prime(); 
	while(~scanf("%d",&n)){
		if(n==0||n==1) printf("无\n");
		if(n%2==0){
			memset(vis,0,sizeof(vis));		//vis记录是否访问过 
			if(dfs(0)); //dfs中记录的是已经添加到b中的个数 
				printf("有\n");	
		} 
		else printf("无\n"); 				//因为当n是奇数的时候，环中肯定有两个奇数相邻，两个奇数相加肯定是偶数 
	}
	
}