注意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