题目描述：
素数环:从1到n这n个数摆成一个环，要求相邻的两个数的和是一个素数。如，n=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
其总数为4
输入：
n的值（n不大于15）
输出：
打印素数环并输出数量，如果不存在素数环则输出 “no solution！”（不输出双引号）。
其实我一开始是用C++写的，但是如果测试集的量级大了之后，iostream用的流要用的时间开销大，所以换成了C语言。
思路：
对于1到n这些数，素数环相当于全排列的子集。
可以试探性的先选一个数，如果下面不符合条件，退回来重新选择。也就是深搜思想。
对于是否是素数，还有这个数是否存在的检查，可以在填方前遍历检查，也可以用空间换时间，建立一个素数数组和是否检查过的数组，降低时间复杂度。
深搜+回溯+剪枝：
#include<stdio.h> int n, sum = 0; void printR(int* r){ for(int i = 0; i < n; i++){ printf("%d ", r[i]); } printf("\n"); } bool isP(int k){ for(int i = 2; i*i <= k; i++){ if(k%i == 0) return false; } return true; } bool check(int* r, int i, int cur){ for(int j = 0; j < cur; j++){ if(r[j] == i || !isP(i+r[cur-1])) return false; } return true; } void dfs(int* r, int cur){ if(cur == n && isP(r[n-1]+r[0])){ printR(r); sum++; return; } for(int i = 2; i <= n; i++){ if(check(r, i, cur)){//剪枝 r[cur] = i; dfs(r,cur+1); //向下深搜 r[cur] = 0; //回溯 } } } int main(){ scanf("%d",&n); int r[n]={0}; r[0] = 1; dfs(r, 1); if(sum == 0) printf("no solution！\n"); return 0; }
空间换时间：
#include<stdio.h> // 改进（空间换时间） const int maxn = 16; int isp[2*maxn+1] = {1}; int vis[maxn+1] = {0}; int r[maxn] = {0}; int n, sum = 0; void printR(){ for(int i = 0; i < n; i++){ printf("%d ", r[i]); } printf("\n"); } void is_prime(int n){ isp[1] = isp[2] = isp[3] = 1; for(int i = 4; i <= n; i++){ for(int j = 2; j*j <= i; j++){ if(i%j == 0){ isp[i] = 0; break; }else isp[i] = 1; } } } void dfs(int cur){ if(cur == n && isp[r[n-1]+r[0]]){ printR(); sum++; return; } for(int i = 2; i <= n; i++){ if(!vis[i] && isp[i+r[cur-1]]){ r[cur] = i; vis[i] = 1;//做标记 // printR(); dfs(cur+1); vis[i] = 0;//取消标记 } } } int main(){ scanf("%d",&n); // n = 16; is_prime(2*maxn);//生成素数表 r[0] = vis[1] = 1; // printR(); dfs(1); // printf("%d\n",sum); if(sum == 0) printf("no solution！\n"); return 0; }
