hdu1016--dfs搜索Prime Ring Problem

//题目的大意就是让你输入一个数n，用这个数生成长度为n的数组，然后这个数组你可以想象成一个循环链表的形式，相邻两个数的和必须是素数，然后输出/

Output

//最后一个数字后面不能有空格，并且输出完所有的可能情况在输出一个空行

#include<iostream>
#include<string.h>
#include<algorithm>
#include<cmath>
using namespace std;
#define inf 0x3f3f3f3f
#define clean(a,b) memset(a,b,sizeof(a))
int t;
int cnt;
bool sign[25];
bool vis[100];
int v[25];
void dfs(int num)
{
	if(num==t&&vis[v[0]+v[t-1]])  //判断最后一个数和第一个数相加是否为素数 
	{
		for(int i=0;i<t-1;i++)
		printf("%d ",v[i]);
		printf("%d\n",v[t-1]);
		return ;
	}
	if(num>=t) return ;
	for(int i=2;i<=t;i++)
	{
		if(!sign[i])
		{
			if(vis[v[num-1]+i])   //如果这个数没有被标记过，就判断和这个数相加是否为素数 
			{
				sign[i]=true;
				v[num]=i;
				dfs(num+1);
				sign[i]=false;
			}
		}
	}
	return ;
}
bool f(int x)
{
	if(x==1) return false;
	for(int i=2;i<=sqrt(x);i++)
	if(x%i==0) return false;
	return true;
}
int main()
{
	clean(vis,false);
	for(int i=1;i<=100;i++)  //素数打表 
	if(f(i))
	vis[i]=true;
	cnt=0;
	while(~scanf("%d",&t))
	{
		clean(sign,false);
		sign[1]=true;
		printf("Case %d:\n",++cnt);
		v[0]=1;  //开头为 1 
		dfs(1);
		printf("\n");
	}
	return 0;
}