【问题描述】将1～n这n个数字首尾相连，形成一个圆环，要求圆环上任意两个相邻的数字之和都是一个素数，请编程输出符合条件的素数环。

输入

输入数据仅一行，包含一个正整数n（n<=20）。

输出

输出数据最多包括20行，每行由n个整数组成，表示前十个符合条件的素数环（不足20个时全部输出）。所有素数环第一个元素必须是1，且按照从小到大的顺序排列。

样例输入 样例输出

样例输入：8

【算法分析】

很明显，这是一道回溯的题目。从1开始，每个空位有n种可能，只要填进去的数满足以下条件：与前面的数不相同并且与左边相邻的数的和是一个素数。第n个数还要判断和第1个数(本题要求第1个数为1)的和是否素数

【算法流程】

1、数据初始化； 2、递归填数：判断第i个数填入是否合法；

A、符合要求：填数；判断是否到达目标（n个已填完）：是，打印结果；不是，递归填下一个；

B、不符合要求：选择下一种可能；

【参考程序】

#include<bits/stdc++.h>using namespace std;int search(int k) ;bool b[21]={0};int a[21]={0};int n,num=0;int main(){	int i,j;	cout<<"请输入:";	cin>>n;	a[1]=1;//首位固定为1	if(n%2==0) //只有偶数个数才可能构成素数环		search(2);	return 0;}bool isprime(int x,int y) //判素数{	if(x+y<2)		return 0;	for(int i=2;i<=sqrt(x+y);i++)	{			if((x+y)%i==0)			return 0;	}		return 1;}int search(int k) // 回溯{	if(num>=20||k>n)//如果超过20种方案退出		return 0;	for(int i=2;i<=n;i++)//从2到n可以选择	{		if(!b[i]&&isprime(a[k-1],i))// 判断相邻数为是否素数、该数是否可用并从小到大排序		{			a[k]=i;			b[i]=1;			if(k==n)			{				if(isprime(a[n],a[1]))				{					num++;					for(int j=1;j<=n;j++)						cout<<a[j]<<' ';					cout<<endl;				}			}					else				search(k+1);			b[i]=0;		}	}}