注意n为奇数时无解

因为无论怎么排列,必然有两个奇数相邻,所以肯定和是偶数,比可能是素数(因为一定比2大)

 1 #include <iostream>
 2 #include <cmath>
 3 using namespace std;
 4 
 5 bool prime[100];
 6 bool used[20];
 7 int sequence[20];
 8 
 9 void output(int n)
10 {
11     for (int i = 0; i < n; i++)
12         if (i!=n-1)
13             cout << sequence[i] << " ";
14         else
15             cout << sequence[i] << endl;
16 }
17 void solve(int step,int n)
18 {
19     if (step==n)
20     {
21         if (prime[(sequence[step-1]+sequence[0])])
22             output(n);
23     }
24     else
25     {
26         for (int i = 2; i <= n; i++)
27             {
28                 if (!used[i])
29                 {
30                     if (prime[(sequence[step-1+ i)])
31                     {
32                         sequence[step] = i;
33                         used[i] = true;
34                         solve(step+1,n);
35                         sequence[step] = 0;
36                         used[i] = false;
37                     }
38                 }
39             }
40     }
41 }
42 int main()
43 {
44     for (int i = 0; i < 100; i++)
45         prime[i] = false;
46     prime[2= true;
47     for (int i = 3; i < 100; i++)
48     {
49         bool is = true;
50         for (int j = 2; j <= sqrt(i+0.0); j++)
51             if (i%j==0)
52             {
53                 is = false;
54                 break;
55             }
56         if (is) prime[i] = true;
57     }
58 
59     int n;
60     int css = 1;
61     while (cin >> n)
62     {
63         cout << "Case " << css++ << ":" << endl;
64         for (int i = 0; i < 20; i++
65         {
66             used[i] = false;
67             sequence[i] = 0;
68         }
69         sequence[0= 1;
70         if (n%2==0) solve(1,n);
71         cout << endl;
72     }
73 
74 //system("pause");
75 return 0;
76 }
77                 
78