素数环-dfs+素数打表

素数环-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是奇数的时候，环中肯定有两个奇数相邻，两个奇数相加肯定是偶数 
	}
	
} 

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
 

文章来源: englishcode.blog.csdn.net，作者：知识浅谈，版权归原作者所有，如需转载，请联系作者。

原文链接：englishcode.blog.csdn.net/article/details/105039223