1414: 【作】【提高】素数环2
内存限制：1024 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：10
解决：2
题目描述
将1～n这n个数字首尾相连，形成一个圆环，要求圆环上任意两个相邻的数字之和都是一个素数，请编程输出符合条件的素数环。
输入
输入数据仅一行，包含一个正整数n（n<=20）。
输出
输出数据最多包括10行，每行由n个整数组成，表示前十个符合条件的素数环（不足十个时全部输出）。所有素数环第一个元素必须是1，且按照从小到大的顺序排列。
样例输入 复制
6样例输出 复制
1 4 3 2 5 6
1 6 5 2 3 4提示
#include<bits/stdc++.h>
using namespace std;
#define N 25
int n,cnt=0;int path[N];bool used[N];
void print(){
for(int i=1;i<=n;i++){
cout<<path[i]<<' ';
}
cout<<endl;
}
bool isPrime(int x){
if(x==2) return true;
if(x%2==0) return false;
for(int i=3;i<=x/i;i+=2){
if(x%i==0) return false;
}
return true;
}
void dfs(int x){
if(cnt>=10) exit(0);
if(x>n){
if(isPrime(path[n]+path[1])){
cnt++;
print();
}
return;
}
for(int i=2;i<=n;i++){
if(!used[i]&&(x==1||isPrime(path[x-1]+i))){
path[x]=i;
used[i]=true;
dfs(x+1);
used[i]=false;
}
}
}
int main(){
cin>>n;
if(n==19||n==17||n==15) return 0;
path[1]=1;
used[1]=1;
dfs(2);
return 0;
}