1086. 【搜索与回溯算法】素数环

时间限制: 1 s

空间限制: 256 MB

题目描述

输入正整数n，把整数1，2，3，……，n组成一个环，使得相邻两个整数之和均为素数。输出时从整数1开始逆时针排列。同一个环应恰好输出一次。按字典序由小到大输出所有可能的排列。

输入

一行，正整数N（1<N <= 16）。

输出

若干行，每行一个符合要求的排列，两个整数之间用一个英文输入法下的空格隔开（半角空格）。如果无符合要求的排列，输出“no answer”，不包含引号，两单词之间有一个半角空格。

样例输入

6

样例输出

1 4 3 2 5 6

1 6 5 2 3 4

me的代码

#include <cstdio>
using namespace std;
int n, f, a[1005], vis[1005];
bool prime (int);
void search (int);
int main()
{
	a[1] = 1;
	vis[1] = 1;
	int n = 0;
	scanf ("%d", &n);
	search (2);
	if (f == 0)
		printf ("no answer");
	return 0;
}
bool prime (int n)
{
	if (n < 2)
		return 0;
	for (int i = 2; i * i <= n; i++)
	{
		if (n % i == 0)
			return 0;
	}	
	return 1;
}
void search (int x)
{
	if (x == n + 1)
	{
		for (int i = 1; i <= n; i++)
			printf ("%d ", a[i]);
		printf ("\n");
		f = 1;
		return;
	}
	else if (x == n)
	{
		for (int i = 1; i <= n; i++)
		{
			if (vis[i] == 0 && prime (a[x - 1] + i) == 1 && prime (a[1] + i) == 1)
			{
				vis[i] = 1;
				a[x] = i;
				search (x + 1);
				vis[i] = 0;
			}
		}
	}
	else
	{
		for (int i = 1; i <= n; i++)
		{
			if (vis[i] == 0 && prime (a[x - 1] + i) == 1)
			{
				vis[i] = 1;
				a[x] = i;
				search (x + 1);
				vis[i] = 0;
			}
		}
	}
}