1 #include <iostream>
 2 using namespace std;
 3 int a[21][21];
 4 int q[21];  //定义一个队列q，存储当前确定的素数环 
 5 int main()
 6 {
 7     bool boo_prime(int);
 8     void f(const int ,int ,int q[21]);
 9     int i,j,n,digit;
10     int count=1;
11     //计算20以内的素数矩阵，存储到二维数组a中 
12     for(i=1;i<=20;i++)
13         for(j=1;j<=20;j++)
14             if(boo_prime(i+j))
15                 a[i][j]=1;
16             else
17                 a[i][j]=0;
18     a[1][1]=0;   
19     //循环输入n，输出每一个n所有符合的素数环 
20     while(cin>>n){
21         digit=1;
22         cout<<"Case "<<count<<":"<<endl;
23         f(n,digit,q);   //调用递归函数f()，输出每种符合的情况 
24         cout<<endl;
25         count++;
26     }
27     return 0;
28 }
29 bool boo_prime(int n)     //判断一个整数n是不是素数 
30 {
31     int i;
32     //判断n是不是素数
33     if(n==1) return false;
34     if(n==2) return true;
35     for(i=2;i<n;i++){
36         if(n%i==0) return false;
37     }
38     return true;
39 }
40 void f(const int n,int digit,int q[21]) 
41 {
42     if(digit==1){    //如果确认到第1位
43         q[1]=1;
44         f(n,digit+1,q);
45     } 
46     else if(digit<=n){      //如果确认到第2~n位
47         int i,j;
48         for(j=1;j<=n;j++){      //循环确定当前位数上的数字是谁 
49             if(a[q[digit-1]][j]==1){     //上一个确认的数字和j之和是否为素数。若是素数，继续向下判断 
50                 bool boo=true;
51                 //如果这个数字就是j的话，它需要不能和前面确定的数字重复
52                 for(i=1;i<digit;i++)
53                     if(j==q[i]){    //如果和前面确定的数字重复的话，令boo=false，说明这种情况不可能；若没有重复，boo默认=true，即下个数字可以是j 
54                         boo=false;
55                         break;
56                     }
57                 if(boo){    //如果这个数字可以是j 
58                     q[digit]=j;         //确认这个数字就是j
59                     if(digit==n){
60                         if(a[j][1]==1)
61                             f(n,digit+1,q);
62                     }
63                     else 
64                         f(n,digit+1,q);     
65                 }
66             }
67         }
68     }
69     else if(digit>n){    //搜索到一种符合的情况，输出 
70         int i;
71         for(i=1;i<=n;i++)
72             if(i==n) cout<<q[i]<<endl;
73             else cout<<q[i]<<‘ ‘;
74     } 
75 }

 1 #include <iostream>
 2 #include <string.h>
 3 using namespace std;
 4 int a[20];    //存储数 
 5 bool isu[20];    //有没有被用过，默认为false（没有） 
 6 int p[38];    //素数表 
 7 bool prime(int n)    //判断某整数是不是素数
 8 {
 9     if(n==2)
10         return true;
11     for(int i=2;i<n;i++){
12         if(n%i==0)
13             return false;
14     }
15     return true;
16 } 
17 void dfs(int s,int n)     //代表第s个数已经确定 
18 { 
19     if(s>=n){
20         if(!p[a[s]+a[1]])
21             return ;
22         for(int i=1;i<n;i++)
23             cout<<a[i]<<‘ ‘;
24         cout<<a[n]<<endl;
25     }
26     else{
27         for(int i=2;i<=n;i++){
28             if(isu[i])
29                 continue;
30             if(!p[a[s]+i])
31                 continue;
32             a[s+1]=i;
33             isu[i]=true;
34             dfs(s+1,n);
35             a[s+1]=0;
36             isu[i]=false;
37         }
38     }
39 }
40 int main()
41 {
42     int n,_count=1;
43     p[0]=1;
44     while(cin>>n){
45         memset(isu,0,sizeof(isu));
46         if(p[0]){
47             //计算38以内的素数矩阵 
48             p[0]=0;
49             for(int i=1;i<=38;i++)
50                 if(prime(i))
51                     p[i]=1;
52                 else
53                     p[i]=0;
54         }
55         a[1]=1;isu[1]=true;
56         cout<<"Case "<<_count++<<‘:‘<<endl;
57         dfs(1,n); 
58         cout<<endl;
59     }
60     return 0;
61 }