c++ 将1～n个数围成一个环 要求相邻两个数的和为素数

以下是使用 C++ 语言实现的将 1~n 个数围成一个环，要求相邻两个数的和为素数的代码示例：

#include <iostream>
#include <vector>
using namespace std;

bool is_prime(int num) {
    if (num < 2) {
        return false;
    }
    for (int i = 2; i <= sqrt(num); i++) {
        if (num % i == 0) {
            return false;
        }
    }
    return true;
}

void prime_circle(int n) {
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        nums[i] = i + 1;
    }
    vector<int> circle(n, -1);
    function<void(int)> search = [&](int k) {
        if (k == n) {
            if (is_prime(circle[0] + circle[n-1])) {
                for (int i : circle) {
                    cout << i << " ";
                }
                cout << endl;
            }
        } else {
            for (int i = 0; i < n; i++) {
                if (find(circle.begin(), circle.begin() + k, nums[i]) == circle.begin() + k) {
                    if (k == 0 || is_prime(nums[i] + circle[k-1])) {
                        circle[k] = nums[i];
                        search(k+1);
                        circle[k] = -1;
                    }
                }
            }
        }
    };
    search(0);
}

int main() {
    prime_circle(6);
    return 0;
}

这个代码实现了将 1~6 个数围成一个环，要求相邻两个数的和为素数的问题。由于这个问题也是 NP 难问题，因此在求解 n 较大时会十分耗时。