1439-素数环2

题目描述

将 1∼n1∼n 这 nn 个数字首尾相连，形成一个圆环，要求圆环上任意两个相邻的数字之和都是一个素数，请编程输出符合条件的素数环。

输入

输入数据仅一行，包含一个正整数 nn（n≤20n≤20）。

输出

输出数据最多包括 1010 行，每行由 nn 个整数组成，表示前十个符合条件的素数环（不足十个时全部输出）。

所有素数环第一个元素必须是 11 ，且按照从小到大的顺序排列。

样例

输入：

6

输出：

1 4 3 2 5 6
1 6 5 2 3 4

解题要求：
1.第1个数必须是1
2.素数环：相邻两个数的和是素数
3.如果超过10个解，只要输出前10个解

解题思路：
1.先输出第1个数为1的全排列
2.加条件使得结果满足环中，任意相邻的2个数的和是素数

3.判断，如果超过10组解，只输出前10组解

特别注意：

如果n是奇数，没有解；因为如果要相邻2数的和是素数，必须一个奇数和一个偶数间隔排开。

如果n是奇数，会导致首尾两个数的和是偶数。

#include <bits/stdc++.h>
using namespace std;/*
解题要求： 
1.第1个数必须是1
2.素数环：相邻两个数的和是素数 
3.如果超过10个解，只要输出前10个解解题思路：
1.先输出第1个数为1的全排列
2.加条件使得结果满足环中，任意相邻的2个数的和是素数
3.判断，如果超过10组解，只输出前10组解 
*/ 
int a[30];//存储素数环 
bool f[30];//标记某个数是否被使用 
int n,cnt = 0;//统计素数环的数量 //判断素数 
bool prime(int n){if(n <= 1) return false;for(int i = 2;i <= sqrt(n);i++){if(n % i == 0) return false;}return true;
}//输出素数环 
void print(){for(int i = 1;i <= n;i++){cout<<a[i]<<" ";}cout<<endl;cnt++;if(cnt == 10) exit(0);
} //为a数组下标为k的位置填值 
void dfs(int k){//循环所有的可能for(int i = 1;i <= n;i++){//如果i没有被用过，且和上一个数的和是素数 if(f[i]==false&&prime(i+a[k-1])){f[i] = true;//标记用过a[k] = i; //判断是否填满n个数，且首尾的和是素数 if(k==n&&prime(a[n]+a[1])) print();//输出素数环的结果else dfs(k+1);//填下一个位置f[i] = false;//回溯：撤销对于i这个数的占用 } } 
} int main(){cin>>n;//如果n是奇数，没有解//因为如果要相邻2数的和是素数，必须一个奇数和一个偶数间隔排开//如果n是奇数，会导致首尾两个数的和是偶数 if(n % 2 == 1) return 0; a[1] = 1;f[1] = true;//1标记占用dfs(2);//从a数组的第2个位置开始填值return 0;
}