素数环-dfs 素数打表(易理解)
代码语言：javascript复制#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是奇数的时候，环中肯定有两个奇数相邻，两个奇数相加肯定是偶数
}
} 
