素数环（信息学奥赛一本通-2110）

【题目描述】

输入正整数n，把整数1,2,…,n 组成一个环，使得相邻两个整数之和均为素数。

【输入】

输入正整数n。

【输出】

输出任意一个满足条件的环。

【输入样例】

6

【输出样例】

4 3 2 5 6 1

【提示】

数据满足：

4≤n≤30

【题解代码】

#include<bits/stdc++.h>
using namespace std;

int n;
bool vis[35];  //标记数组
int cnt[35];  //存储每一层的数据
bool flag = false;  //作为是否已经找到的标记，用于剪枝
//
// 判断是否是素数
// 
// 朴素法：（数据量较小时可以使用该种方法）
//bool isprime(int x)
//{
//	if (x < 2) return false;
//	for (int i = 2; i <= sqrt(x); i++)
//	{
//		if (x % i == 0) return false;
//	}
//	return true;
//}

//埃氏筛法：将素数的倍数全部筛掉，留下的就是素数
bool isprime[100];  //标记数组   0-是素数   1-不是素数
void E_sieve(int x)
{
	isprime[0] = isprime[1] = 1;  //0和1都不是素数
	for (int i = 2; i * i <= x; i++)
	{
		if (isprime[i] == 0)  //i是素数
		{
			for (int j = i * i; j <= x; j += i)  //n之内的i的所有倍数都不是素数
			{
				isprime[j] = 1;
			}
		}
	}
}

void dfs(int depth)
{
	if (depth > n)
	{
		if (isprime[cnt[1] + cnt[depth - 1]]) return;  //如果首尾之和不是素数
		for (int i = 1; i < depth; i++)
		{
			printf("%d ", cnt[i]);
		}
		flag = true;
		return;
	}
	for (int i = 1; i <= n; i++)
	{
		if ((depth==1 && !vis[i]) || (depth > 1 && !vis[i])&& !isprime[i+cnt[depth-1]])  
		{
			cnt[depth] = i;
			vis[i] = 1;
			dfs(depth + 1);
			vis[i] = 0;
			if (flag) return;  //如果已经找到了，直接逐层返回即可，不需要继续寻找
		}
	}
}

int main()
{
	cin >> n;
	E_sieve(2 * n);
	dfs(1);
	return 0;
}