C++ 素数環問題をどのように解決するか

C++の素数環問題は、バックトラックアルゴリズムで解決できます。以下にその解決策のサンプルコードを示します。

#include <iostream>
#include <vector>
using namespace std;
bool isPrime(int num) {
if (num < 2) {
return false;
}
for (int i = 2; i * i <= num; i++) {
if (num % i == 0) {
return false;
}
}
return true;
}
void backtracking(int n, vector<int>& nums, vector<bool>& visited) {
if (nums.size() == n && isPrime(nums.front() + nums.back())) {
for (int num : nums) {
cout << num << " ";
}
cout << endl;
return;
}
for (int i = 2; i <= n; i++) {
if (visited[i]) {
continue;
}
if (isPrime(nums.back() + i)) {
visited[i] = true;
nums.push_back(i);
backtracking(n, nums, visited);
nums.pop_back();
visited[i] = false;
}
}
}
void primeRing(int n) {
vector<int> nums;
vector<bool> visited(n + 1, false);
nums.push_back(1);
visited[1] = true;
backtracking(n, nums, visited);
}
int main() {
int n;
cout << "Enter the value of n: ";
cin >> n;
cout << "Prime rings of size " << n << ":" << endl;
primeRing(n);
return 0;
}

上記コードでは、isPrime()関数は数が素数かどうかを調べます。backtracking()関数は再帰を使用して、素数環の全てのパターンを生成するためにバックトラックアルゴリズムを使用します。primeRing()関数は開始点の初期化と問題を解決するためにbacktracking()関数を呼び出します。最後に、ユーザー入力を使用してmain関数を実行し、全ての素数環を出力します。