思路与算法

先筛出2..2n的素数。任意旋转不改变合法性，可固定第一项为1；再回溯填入尚未使用且与末项和为素数的数。候选按剩余邻居数排序只改善搜索顺序，不删分支。最后一项还须与1的和为素数。奇数n直接无解。

正确性说明

互异正整数相邻之和若为素数，不可能等于2，所以必须为奇数，即相邻项奇偶相反。因此奇数长度不能闭合。对于偶数，固定1不漏环，因为每个合法环都能旋转到1开头；回溯穷尽所有允许下一项，闭口检查确保完整环正确。整个4..30域的每个偶数已另有独立合法环证书。

复杂度

筛初始化O(n log log n)，回溯最坏为阶乘级枚举，候选排序至多O(n log n)每层；空间O(n²)内的邻接位集和路径、素数表。本题只求一个证书，完整27个n值均在原资源实际验证，不把最坏搜索写成多项式。

易错点

必须检查最后与最初相邻。允许旋转和反向，不要把某个样例顺序当唯一答案。No solution仅用于无解，本地奇数范围都有明确奇偶证明。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> path;
vector<bool> prime;
unsigned long long adj[31];
bool dfs(unsigned long long used) {
    int at = path.back();
    if ((int)path.size() == n)
        return prime[at + 1];
    unsigned long long all = (1ULL << (n + 1)) - 2, un = all & ~used;
    vector<pair<int, int>> moves;
    for (int v = 2; v <= n; ++v)
        if ((un >> v & 1) && prime[at + v]) {
            if ((int)path.size() == n - 1 && !prime[v + 1])
                continue;
            int degree = __builtin_popcountll(adj[v] & un);
            moves.push_back({degree, v});
        }
    sort(moves.begin(), moves.end());
    for (auto item : moves) {
        int v = item.second;
        path.push_back(v);
        if (dfs(used | (1ULL << v)))
            return true;
        path.pop_back();
    }
    return false;
}
int main() {
    cin >> n;
    if (n % 2) {
        cout << "No solution\n";
        return 0;
    }
    prime.assign(2 * n + 1, true);
    prime[0] = prime[1] = false;
    for (int i = 2; i * i <= 2 * n; ++i)
        if (prime[i])
            for (int j = i * i; j <= 2 * n; j += i)
                prime[j] = false;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            if (i != j && prime[i + j])
                adj[i] |= 1ULL << j;
    path = {1};
    if (!dfs(2)) {
        cout << "No solution\n";
        return 0;
    }
    for (int i = 0; i < n; ++i)
        cout << (i ? " " : "") << path[i];
    cout << '\n';
}