PRime Ring Problem

68 Sample Output
Case 1:1 4 3 2 5 61 6 5 2 3 4Case 2:1 2 3 8 5 6 7 41 2 5 8 3 4 7 61 4 7 6 5 8 3 21 6 7 4 3 8 5 2
#include<stdio.h>#include<string.h>#define max 21int a[max];int vis[max];int n;int Case=1;/*  判断是否为素数的一个函数*/int isp(int i){  if(i==1||i==2)	  return 1;  else 	  for(int j=2;j<i;j++)		  if(i%j==0)			  return 0;		  return 1;}/*  搜索函数的构造*/void dfs(int cur){  if(cur==n&&isp(a[0]+a[n-1]))//也可以说是边界判断吧，当搜索的cur到了n时，就可以停止了，注意还要判断第一个和最后一个是否相等  {     for(int i=0;i<n-1;i++)		 printf("%d ",a[i]);	 printf("%d",a[n-1]);//格式控制	 printf("/n");  }  else	  for(int i=2;i<=n;i++)//依次往后面进行判断	     if(!vis[i]&&isp(i+a[cur-1]))//判断这个数是否被用过，算是剪枝吧，然后判断当前的数和前面这个数和是否为素数		 {		   a[cur]=i;//如果是素数的话就把这个值赋值到这个表里面		   vis[i]=1;//标记这个数已经用过		   dfs(cur+1);//继续回溯，搜索下面这个数的一条新的素数路径		   vis[i]=0;//再把值回到原来的		 }}int main(){  while(scanf("%d",&n)!=EOF)  {    memset(vis,0,sizeof(vis));	a[0]=1;//将搜索值为1	printf("Case %d:/n",Case);	dfs(1);//搜索为1从一开始进行搜索	Case++;	printf("/n");  }  return 0;}