杭电1016

DFS深度优先搜索
 1 #include<stdio.h>
 2 
 3 int prime[40],a[20],v[20];
 4 
 5 void ss();
 6 void dfs(int,int);
 7 
 8 int main()
 9 {
10     ss();
11     int Case=0,n;
12     while(~scanf("%d",&n))
13     {
14         printf("Case %d:
",++Case);
15         a[1]=1;
16         dfs(2,n);
17         printf("
");
18     }
19 }
20 
21 void ss()
22 {
23     int i,j;
24     prime[0]=prime[0]=1;
25     for(i=2; i*i<=40; ++i)
26         if(!prime[i])
27             for(j=i*i; j<40; j+=i)
28                 prime[j]=1;
29 }
30 
31 void dfs(int x,int y)
32 {
33     int i;
34     if(x==y+1 && !prime[a[y]+1])
35     {
36         for(i=1; i<=y; ++i)
37             if(i==1)
38                 printf("%d",a[i]);
39             else
40                 printf(" %d",a[i]);
41         printf("
");
42         return ;
43     }
44     for(i=2; i<=y; ++i)
45     {
46         if(!v[i] && !prime[i+a[x-1]])
47         {
48             a[x]=i;
49             v[i]=1;
50             dfs(x+1,y);
51             v[i]=0;
52         }
53     }
54 }