Prime Ring Problem（素数环问题）

A ring is compose of n circles as shown in diagram. Put natural number 1, 2, ..., n into each circle separately, and the sum of numbers in two adjacent circles should be a prime.

Note: the number of first circle should always be 1.

 

Input

n (0 < n < 20).

Output

The output format is shown as sample below. Each row represents a series of circle numbers in the ring beginning from 1 clockwisely and anticlockwisely. The order of numbers must satisfy the above requirements. Print solutions in lexicographical order.

You are to write a program that completes above process.

Print a blank line after each case.

Sample

Inputcopy	Outputcopy
6 8	Case 1: 1 4 3 2 5 6 1 6 5 2 3 4 Case 2: 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

中文题意：

如图所示，一个环由 n 个圆组成。将自然数 1, 2, ..., n 分别放入每个圆圈中，相邻两个圆圈中的数字之和应为素数。

注意：第一个圆圈的数量应始终为 1。

 

输入

n (0 < n < 20)。

输出

输出格式如下面的示例所示。每行代表圆环中从 1 开始顺时针和逆时针方向的一系列圆圈数字。数字的顺序必须满足上述要求。按字典顺序打印解决方案。

您将编写一个完成上述过程的程序。

在每个案例之后打印一个空行。

 

 AC代码：

#include<iostream>
#include<string>
#include<math.h>
#include<algorithm>
#include<map>
#include<set>
#include<string.h>
#include<queue> 
using namespace std;
int num[21];
int vis[21];//标记是否被使用
int n;
bool prime(int x){//使用六素数法判断素数
	if(x<=1)return false;
	if(x==2||x==3||x==5)return true;
	if(x%2==0||x%3==0)return false;
	for(int i=5;i<=sqrt(x);i+=5){
		if(x%i==0||x%(i=2)==0)return false; 
	}
	return true;
}
void dfs(int cnt){
	if(cnt==n&&prime(1+num[n-1])){//满足条件就输出
		for(int i=0;i<n;i++){
			if(i!=n-1)cout<<num[i]<<" ";
			else cout<<num[i]<<endl;
		}
		vis[num[n-1]]=0;//用完最后一个数也将其置位0
	}
	if(cnt==n)return;
	for(int i=2;i<=n;i++){	
		if (vis[i]==0&&prime(num[cnt-1]+i)){//满足下一次搜索条件
			vis[i]=1;
			num[cnt]=i;
			dfs(cnt+1);//搜索下一次
			vis[i]=0;//切记归位
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int T=1;
	while(cin>>n){
		memset(vis,0,10);
		num[0]=1;//确保每一次的第一个都是1
		vis[1]=1;//标记1已经使用了
		cout<<"Case "<<T++<<":"<<endl; 
		dfs(1);
		cout<<endl;
	}
	
}

 使用stl库中的next_permutation函数但TLE代码：

#include<iostream>
#include<string>
#include<math.h>
#include<algorithm>
#include<map>
#include<set>
#include<string.h>
#include<queue> 
using namespace std;
int a[22];

bool solve(int x,int y){
	if(x+y==2||x+y==5||x+y==3)return false;
	if((x+y)%2==0||(x+y)%3==0)return true;
	for(int i=5;i<=sqrt(x+y);i+=5){
		if((x+y)%i==0||(x+y)%(i+2)==0)return true;	
	}
	return false;
}
int main(){
	int n;
	int T=1;
	while(cin>>n){
		for(int i=0;i<n;i++)a[i]=i+1;
		int cnt=1;
		do{
			bool flag=true;
			for(int i=1;i<n;i++){
				if(solve(a[i],a[i-1])){
					flag=false;
					break;
				}
			}
			if(solve(a[0],a[n-1]))flag=false;
			if(flag){
				if(cnt==1)cout<<"Case "<<T++<<":"<<endl;
				cnt=2;
				for(int i=0;i<n;i++){
					if(i!=n-1)cout<<a[i]<<" ";
					else cout<<a[i]<<endl; 
				}
			}
		}while(next_permutation(a+1,a+n));
		T++;
		cout<<endl;
	}
	return 0;
}