素数环 Primg Ring Problem

素数环

题目链接：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=84562#problem/C

题意：

输入正整数n，把整数1~n组成一个环，使相邻的两个整数之和均为素数。输出时从整数1开始逆时针排列。

同一个环应恰好输出一次。n<=16

Sample Input

6
8

Sample Output

Case 1:
1 4 3 2 5 6
1 6 5 2 3 4

Case 2:
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2


分析：
 因为每个环对应一个排列，且排列总数高达2*10^13，为了防止超时用回溯法。

 1 #include<iostream>
 2 #include<cmath>
 3 #include<cstring>
 4 using namespace std;
 5 int vis[20],a[20];
 6 int n;
 7 bool is_prime(int m)
 8 { if(m<=3) return true;  
 9     int y=(int)sqrt(m);  
10 for(int j=2;j<=y;j++)
11 if(m%j==0)  return false;
12  return  true;
13  }
14 void dfs(int cur)
15 { 
16 if(cur==n&&is_prime(a[0]+a[n-1]))  //递归边界（测试第一个和最后一个数）
17   {
18     for(int j=0;j<n-1;j++)
19       cout<<a[j]<<' ';
20     cout<<a[n-1]<<endl;
21   }
22    else
23    {
24     for(int i=2;i<=n;i++) 
25     { if(!vis[i]&&is_prime(i+a[cur-1]))  //如果i没有用过，并且与前一个数之和为素数
26       {
27        a[cur]=i;
28        vis[i]=1;                   //设置标志
29        dfs(cur+1);
30         vis[i]=0;                  //清除标志
31       }
32     }
33    }
34 }
35 int main()
36 {
37     int t=0;
38 while(cin>>n)
39 { 
40     
41     memset(a,0,sizeof(a));
42     memset(vis,0,sizeof(vis));
43     a[0]=1;    
44     if(t++) cout<<endl;
45     cout<<"Case "<<t<<':'<<endl;
46     dfs(1);
47 }
48 return 0;
49 }