解题思路

素数环：把 1~n 摆成一个环，任意相邻两个数的和都是素数，输出所有摆法。

思路：回溯（深度优先搜索）。

把环看成 n 个位置，从第一个位置开始逐个填数：

1. 对当前位置，尝试放 1~n 中还没用过的数
2. 放之前检查：这个数和上一个数之和是不是素数
3. 是素数就放下去，标记已用，递归下一个位置
4. 如果所有位置都填好了，再检查第一个和最后一个的和是不是素数，是就输出
5. 回溯恢复标记，试下一个数

为什么用回溯？ 素数环的摆放方案非常多，回溯能边放边剪枝（不满足素数和就不继续），比穷举所有排列快得多。

举例：n=4 有 8 种摆放，比如 1 2 3 4（1+2=3、2+3=5、3+4=7、4+1=5 都是素数）。

参考代码

#include <iostream>
using namespace std;

int n, a[11], book[11], cnt;

bool isPrime(int x) {
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) return false;
    }
    return true;
}

void dfs(int pos) {
    if (pos == n) {
        if (isPrime(a[n - 1] + a[0])) {  // 首尾也相邻
            cnt++;
            cout << cnt << ":";
            for (int i = 0; i < n; i++) cout << a[i] << " ";
            cout << endl;
        }
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (book[i]) continue;
        if (pos > 0 && !isPrime(a[pos - 1] + i)) continue;  // 和上一位和是素数
        a[pos] = i;
        book[i] = 1;
        dfs(pos + 1);
        book[i] = 0;  // 回溯
    }
}

int main() {
    cin >> n;
    dfs(0);
    cout << "total:" << cnt << endl;
    return 0;
}

复杂度分析

• 时间复杂度：约 O(N!)，回溯剪枝
• 空间复杂度：O(N)，递归深度加标记数组