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;}