素数环问题

将从1到n这n个整数围成一个圆环，
若其中任意2个相邻的数字相加，结果均为素数，那么这个环就成为素数环。

现要求输入一个n，求n个数围成一圈有多少种素数环，
规定第一个数字是1。写出相应的的算法思想并编程实现。

样例：
(1) 

input: 

6
output:

1 4 3 2 5 6
1 6 5 2 3 4

(2) 

input:

8
output:

1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2

#include <iostream>
#include <cstdio>//printf()
#include <cstring>
#include <cmath>//取根号函数sqrt()
using namespace std;
//参考1 https://blog.csdn.net/qq_36963214/article/details/98777767
//参考2 https://blog.csdn.net/u011590573/article/details/80030522
/***
将从1到n这n个整数围成一个圆环，
若其中任意2个相邻的数字相加，结果均为素数，那么这个环就成为素数环。现要求输入一个n，求n个数围成一圈有多少种素数环，
规定第一个数字是1。写出相应的的算法思想并编程实现。
样例：
(1)6
1 4 3 2 5 6
1 6 5 2 3 4
(2)8
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2***/
int n;//素数环中数字的个数n，需要用从1到n的数围成素数环
int num[25];//存放满足素数环要求并被采用的数字，共n个数字
int used[25];//表示第i个数i是否被用掉了，置1为被使用，置0为未被使用
int sum;//记录总共有多少种素数环
void dfs(int x);//深度遍历查找所有素数环，参数表示已经有x个数被采用
bool isPrime(int);//判断是否是素数int main()
{sum = 0;memset(used, 0, sizeof(used));//初始化记录数组，令used[1]到used[n]都置0memset(num, 0, sizeof(num));num[1] = 1;//数值1作为素数环的第一个数used[1] = 1;//数值1被使用，标记为1cin >> n;if(n % 2 == 1)  sum = 0;//当n为奇数时，有奇数个数字，//则必会出现两个奇数相加的情况，由于两个奇数的和不为素数，所以素数环不成立。else  dfs(1);//第一个数固定为 1cout << "素数环的数量:" << sum << endl;return 0;
}
void dfs(int x)
{//x 代表 已经有x个数被采用，num[x]代表最后一个被采用数的值if(x == n && isPrime(num[1]+num[n]) == 1){//递归结束条件：x=n时表示已经有n个数形成素数环(满足题目要求)//并且 1+num[n] 的和为素数(num[1]=1，num[n]是第n个被采用的数)//因为是一个环，所以最后一个被采用的数num[n]会和第一个数num[1]相邻，所以两者之和需要为素数sum++;//素数环个数加1
//        /*for(int i = 1; i <= n; i++)//如果需要输出素数环，用这个循环{if(i == 1){printf("%d", num[i]);}else{printf(" %d", num[i]);}}cout << endl;//输出完一个素数环后要换行
//        */return;}else{for(int i = 2; i <= n; i++){//从数值2开始遍历，每一层dfs都遍历，寻找所有的素数环if(used[i] == 0 && isPrime(i + num[x]))//num[x]表示第x个被采用数的值{//如果数值i未被使用并且与 最后一个被录入环中的数 和为素数num[x + 1] = i;//记录环中第x+1个数的值为 iused[i] = 1;//标记数值i被使用dfs(x + 1);//继续搜索环中第x+1个数字used[i] = 0;//递归回来后，used[i]置0，表示数值i未被使用，//虽然数值i之前已经被用过找环了，但是回来置0可以继续搜索其他可能的环}}}return;
}
bool isPrime(int k)
{//判断参数k是否为素数if(k == 2)//当参数为2时，要特殊判断（2为素数）return true;else{int x = sqrt(k);//计算传入参数k的平方根值，可提高判断素数的效率for(int i = 2; i <= x; i++){if(k % i == 0)  return false;}}return true;
}