题目： 把从1到n这n个数摆成一个环，要求相邻两个数的和是一个素数，求出所有解法。

思路：
用数组a模拟n个数组成的环。

递归地填数：
判断第 k 种可能是否合法，
如果合法则填数；判断是否到达目标（n个数已填完），是则输出，不是则递归填下一个
如果不合法则选择下一种可能；

完整代码+注释

# include<stdio.h>
# include<math.h>int a[20];						//用数组模拟n个数组成的环int check_1(int x, int i);		//判断数是否重复
int check_2(int x);				//判断一个数是否为素数
int check_3(int x, int i);		//判断相邻两数之和是否为素数
void Output_Num();				//输出函数
int n, count = 0;/*填数，填第i+1个数（i从0开始）*/
void Insert_Num(int i) {int k;for (k = 2; k <= n; k++) {if (check_1(k, i) && check_3(k, i)) {a[i] = k;			//符合条件则将数k填入a数组中if (i == n - 1) {Output_Num();	//满n个数（i从0开始）则填数完成，输出count++;}else {Insert_Num(i + 1);	//填下一个数a[i] = 0;			//回溯，置a[i]=0}}}
}/*判断数x是否与数组a中前i个元素重复*/
int check_1(int x, int i) {int k;for (k = 0; k < i; k++) {if (a[k] == x)return 0;}return 1;
}/*判断数x是否为素数*/
int check_2(int x) {int k, a;a = sqrt(x);for (k = 2; k <= a; k++) {if (x % k == 0)return 0;}return 1;
}/*判断数x和它相邻的前一个数a[i-1]之和是否为素数*/
int check_3(int x, int i) {if (i < n - 1)return (check_2(x + a[i - 1]));elsereturn (check_2(x + a[i - 1]) && check_2(x + a[0]));//最后一个数还需判断和第一个数之和是否为素数
}/*输出函数，打印素数环*/
void Output_Num() {for (int j = 0; j < n; j++)printf("%d ", a[j]);printf("\n");
}int main() {int k;printf("请输入n：");scanf("%d", &n);for (k = 0; k < n; k++)a[k] = 0;			//初始化为0a[0] = 1;				//第一个数放1Insert_Num(1);			//调用函数填第二个数if (count == 0)printf("\nNo Answer！\n");elseprintf("\n共有%d种解法\n", count);return 0;
}

运行结果
（1）n=8时
（2）n=10时