美丽的项链（素数环）（回溯法）

520马上就要到了，丁丁妹在思考送自己的室友什么礼物能够彰显她深深的室友之爱。
由于丁丁妹最近沉迷于数学，于是她想出了一个绝（土）妙（味）的礼物——素数项链。
具体而言，素数项链是一个由1~n共n个数排列而成的环，环中任意相邻两个数的和都是素数，如下图就是这样的一条项链：

现在丁丁妹已经买了n个数字，就等着把它们串起来了，她希望知道，素数环一共有多少种可能的情况。
考虑到对称性，我们假设素数环的元素都是从11开始的。

单组数据，第一行为一个正整数nn，表示素数环中元素的个数。
数据保证：0 输出描述

所有可能的素数环，按字典序从小到大输出。

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

也是一道很常规的回溯算法题。因为是环，可以先固定第一个位置，之后一次向后面的位置填充数字，但有许多优化剪枝的技巧：

1、n为奇数时，不可能构成素数环，可以简单去想一下

2、可以在构成换之前，就对相邻数字之和进行判断是否为奇数，不是可直接剪枝

3、因为题目原因，两数和最大为39，可以人工直接去完成判断是否为素数，不用for循环了，节省了非常多的时间

#include
#include
#include
using namespace std;
int n;
vector res(21);
vector tag(21);
bool shisushu(int x)
{
	if(x==2||x==3||x==5||x==7||x==11||x==13||x==17||x==19||x==23||x==29||x==31||x==37)
		return 1;
	else
		return 0;
}

void dfs(int k)
{

	if(k>=n&&shisushu(res[0]+res[n-1]))
	{
		for(int i=0; i>n;
	if(n%2==1)
	{
		return 0;
	}
	res[0]=1;		//从1开始
	tag[1]=1;
	dfs(1);
	return 0;
}