Prime Ring Problem（搜索）

http://acm.hdu.edu.cn/showproblem.php?pid=1016
/*
题意;
给你一个数n ，求出所有的排列 这些排列的特征是任意相邻的两数只和是素数，而且首位只和也是素数
*/

include

include

include

int nZ,t,k;
int primAyyr[21];//已找到的素数排列
bool vis[21];//标记是否访问过
bool isPrim(int n)//判断素数
{
if(n0||n1)return false;
for(int i=2; i*i<=n; i++)
if(n%i0)return false;
return true;
}
void dfs(int n)
{
if(nnZ)
{
if (isPrim((primAyyr[0]+primAyyr[n-1])))//判断首尾之和是否为素数
{
printf("1");
for(int i=1; i<nZ; i++)
printf(" %d",primAyyr[i]);//最后一个没有空格
printf(" ");
}
return;
}
for(int i=2; i<=nZ; i++)//题目要求每次都是从1开始的，所以1就不用算了
{
if(isPrim(primAyyr[n-1]+i)&&vis[i])
{
primAyyr[n]=i;
vis[i]=false;
dfs(n+1);
vis[i]=true;
}
}
return;
}
int main()
{
int n;
while(~scanf("%d",&nZ))
{
printf("Case %d: ",++t);
memset(vis,true,sizeof(vis));
primAyyr[0]=1;
vis[0]=false;
dfs(1);
printf(" ");
}

return 0;

}