Problem.png
直接生成所有排列再判断的话会超时，因此需要递归回溯剪枝。
每确定排列中的一位数，就要检查相邻两位的和是否为素数，如果是素数，才继续递归，否则返回上层调用。
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
using namespace std;
bool isprime(int num) {
for (int i = 2; i <= round(sqrt(num)); i++) {
if (num % i == 0) {
return false;
}
}
return true;
}
void print_permutation(int n, int* A, int cur) {
if (cur == n) {
// 所有相邻数的和都为素数时
// 才将排列打印出来
if (isprime(A[cur - 1] + A[cur % n])) {
cout << A[0];
for (int i = 1; i < n; i++) {
cout << ' ' << A[i];
}
cout << endl;
}
}
else {
for (int i = 2; i <= n; i++) {
bool ok = true;
for (int j = 1; j < cur; j++) {
if (i == A[j]) {
ok = false;
break;
}
}
if (ok) {
A[cur] = i;
// 递归回溯剪枝
// 每确定排列中的一位数，就要检查相邻两位的和是否为素数
// 如果是素数，才继续递归，否则返回上层调用
if (isprime(A[cur - 1] + A[cur])) {
print_permutation(n, A, cur + 1);
}
}
}
}
}
int main() {
int n;
int t = 0;
while (cin >> n) {
int A[20] = {0};
A[0] = 1;
if (t) {
printf("\n");
}
t++;
printf("Case %d:\n", t);
print_permutation(n, A, 1);
}
return 0;
}
