题目描述

将从1到n，n个整数摆成一个环，若其中任意2个相邻的数字相加，结果均为素数，那么这个环就成为素数环。

输入

一行一个整数 n，代表有多少个数字。n <= 20；

输出

输出素数环。

样例输入

6复制

样例输出 

1 4 3 2 5 6
1 6 5 2 3 4
2 3 4 1 6 5
2 5 6 1 4 3
3 2 5 6 1 4
3 4 1 6 5 2
4 1 6 5 2 3
4 3 2 5 6 1
5 2 3 4 1 6
5 6 1 4 3 2
6 1 4 3 2 5
6 5 2 3 4 1复制

类似题目链接：回溯法——素数环（两种方法解题）_回溯法求解素数环-CSDN博客 

这道题是在考dfs(深搜)  代码如下： 

#include<bits/stdc++.h>//万能头
using namespace std;
int n,bj[100005],ans[100005];
int dp(int sus){
    long long i; 
    if(sus<=1) return 0;
    for(i=2;i<=sqrt(sus);i++){
        if(sus%i==0){return 0;} 
    }
	return 1; 
}
void dfs(int x){
	if(x>n){
		if(dp(ans[1]+ans[n])){
			for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
			cout<<"\n";
		}
		return ;
	}
	for(int i=1;i<=n;i++){
		if(x==1||dp(ans[x-1]+i)&&bj[i]==0){
			ans[x]=i;
			bj[i]=1;
			dfs(x+1);
			bj[i]=0;
		}
	}
	return ;
}
int main(){
	cin>>n;
	memset(bj,0,sizeof(bj));
	dfs(1);
	return 0;
}
复制