hdu 1016 Prime Ring Problem (素数环)

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 int visit[22],q[100],n;
 6 int sushu(int n)
 7 {
 8     int i;
 9     for (i=2; i*i<=n; i++)
10         if (n%i==0)
11             return 0;
12     return 1;
13 }
14 void dfs(int x,int y)
15 {
16     int i;
17     q[x]=y;
18     visit[y]=1;
19     if(x==n)
20     {
21         if(sushu(q[x]+q[1]))
22         {
23             printf("1");
24             for(i=2; i<=n; i++)
25                 printf(" %d",q[i]);
26             printf("
");
27         }
28         return ;
29     }
30     for(i=1; i<=n; i++)
31     {
32         if(!visit[i]&&sushu(q[x]+i))
33         {
34             dfs(x+1,i);
35             visit[i]=0;
36         }
37     }
38     return ;
39 }
40 int main()
41 {
42     int flag=1;
43     while(scanf("%d",&n)!=EOF)
44     {
45         printf("Case %d:
",flag++);
46         memset(visit,0,sizeof(visit));
47         dfs(1,1);
48         printf("
");
49     }
50     return 0;
51 }