一个大小为N(N<=17)的质数环是由1到N共N个自然数组成的一个数环，数环上每两个相邻的数字之和为质数。如下图是一个大小为6的质数环。为了方便描述，规定数环上的第一个数字总是1。如下图可用1 4 3 2 5 6来描述。若两个质数环，数字排列顺序相同则视为本质相同。现在要求你求出所有本质不同的数环。

只有一个数N，表示需求的质数环的大小。如：

每一行描述一个数环，如果有多组解，按照字典序从小到大输出。如：

6

1 4 3 2 5 6

1 6 5 2 3 4

n<=17

对代码不做解释，貌似标程就是我的代码，普通的DFS就行，建议用数组保存每个数是否是质数，这样可以省去重复判断质数的时间，而且使代码更简单

#include <stdio.h>#define MAXN 1000int prime[MAXN],sol[MAXN],used[MAXN],n;//prime[i]=1表示i是质数,sol[i]=当前输出方案中环上第i个数,used[i]=当前输出方案中环上第i个数int isprime(int in) //是质数返回1，不是返回0{	int i;	for(i=2;i<in;i++)		if(in%i==0)			return 0;	return 1;}void dfs(int m) //填写环上第m个数{	int i,j;	if(m>n) //最后一个数已经填写完	{		for(j=1;j<=n;j++)			printf("%d ",sol[j]);		printf("\n");		return;	}	for(i=2;i<=n;i++)	{		if(used[i]==0&&prime[sol[m-1]+i]) //数字i没有用过且i与第m-1个数之和为质数		{			used[i]=1;			sol[m]=i;			if(m<n) dfs(m+1);			else if(prime[sol[1]+i]) dfs(m+1);			sol[m]=0;			used[i]=0;		}	}}int main(){	int i;	scanf("%d",&n);	for(i=2;i<=2*n;i++)		prime[i]=isprime(i);	used[1]=1; //数字1被用过了	sol[1]=1; //第一个数是数字1	dfs(2);	return 0;}