【问题描述】
素数环是一个计算机程序问题，指的是将从1到n这n个整数围成一个圆环，若其中任意2个相邻的数字相加，结果均为素数，那么这个环就成为素数环。
现在要求输入一个n，求n个数围成一圈有多少种素数环，规定第一个数字是1，将所有可能情况输出并输出总的个数。
【样例输入】
6
【样例输出】
1 4 3 2 5 6
1 6 5 2 3 4
2
问题解析：
分析题意，从1开始，每个空位有n种可能，只要填进去的数合法，合法条件如下：
1）与前面的数不相同；
2）与左边相邻的数的和是一个素数；
3）第n个数和第1个数的和为素数。
我们可以定义一个一维数组a，每个位置可以想象成一个盒子，n个数字放入1到n号盒子当中，变量step表示当前正处在第step个小盒子面前。1号盒子中放入数字1，从2号盒子开始进行搜索，从小到大循环判断数字2-n，如果数字i之前未被使用过且满足素数环的条件则将a[step]=i;同时需要定义book数组来标记哪些数字已经使用过。
完整代码参考：
#include <iostream>
#include <cmath>
using namespace std;
//定义a数组存储构成素数环的1-n个数字，book数组为标记数组，记录每个数字是否用过，放置重复使用
int a[21],book[21];
//记录构成素数环的总的个数
int total = 0;
int n;
//定义判断是否为素数的函数
bool is_prime(int n) {
if(n == 1|| n == 0) {
return false;
}
for(int i= 2; i <= sqrt(n); i++) {
if(n%i==0){
return false;
}
}
return true;
}
//定义深搜函数
void dfs(int step) { //step表示现在站在第几个盒子面前
int i;
//如果站在第n+1个盒子面前，则表示前n个盒子已经放好，并且满足首尾和仍为素数则输出此序列，并将total的值加1
if(step ==n+1 && is_prime(a[n]+a[1])) {
for(i= 1; i <= n; i++) {
cout<< a[i] << ” “;
}
cout<< endl;
total++;
return;
}
//否则遍历数字2-n
for(i = 2;i <= n; i++) {
//如果i还未被填入，且i与前一个数的和为素数
if(book[i]==0&& is_prime(i+a[step-1])) {
//将i存入到第step个盒子中
a[step]= i;
//将book[i]标记为1，表示i已经使用过
book[i]= 1;
//通过函数递归调用实现
dfs(step+1);
//当dfs函数返回时，一定要将i的值收回，才能进行下一次的尝试，这一步非常重要
book[i]= 0;
}
}
return;
}
int main() {
cin>> n;
//由于规定第一个数字为1，则将a[1]初始化为1，同时将数字1标记为已使用过
a[1]=1;
book[1]=1;
//调用深搜函数dfs
dfs(2);
//输出最后总的个数
cout<< total << endl;
return 0;
}
转自公众号：
noip案例讲解