Prime Ring Problem

http://acm.hdu.edu.cn/showproblem.php?pid=1016
View Code
 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std ;
 4 int vis[20], a[20] ;
 5 bool prime[40] ;
 6 void init()
 7 {
 8     prime[1] = 1 ;
 9     for(int i=2; i<=40; i++)
10     {
11         prime[i] = 1 ;
12         for(int j=2; j*j<=i; j++)
13         {
14             if(i%j==0)
15             {
16                 prime[i] = 0 ;
17                 break ;
18             }
19         }
20     }
21 }
22 void dfs(int num, int n)
23 {
24     if(num>n&&prime[a[1]+a[n]])
25     {
26         for(int i=1; i<n; i++)
27         cout<<a[i]<<" " ;
28         cout<<a[n]<<endl ;
29     }
30     for(int i=2; i<=n; i++)
31     {
32         if(!vis[i]&&prime[a[num-1]+i])
33         {
34             vis[i] = 1 ;
35             a[num] = i ;
36             dfs(num+1, n) ;
37             vis[i] = 0 ;
38         }
39     }
40 }
41 int main()
42 {
43     int n, num = 1 ;
44     init() ;
45     a[1] = 1 ;
46     while(cin>>n)
47     {
48         cout<<"Case "<<num++<<":"<<endl ;
49         if(n%2==0)
50         {
51             memset(vis, 0, sizeof(vis)) ;
52             dfs(2, n) ;
53         }
54         cout<<endl ;
55     }
56     return 0 ;
57 }