蓝桥杯备赛 Day14 素数环

信息学奥赛一本通（C++版）在线评测系统

【题目描述】

输入正整数nn，把整数11,22,…,nn 组成一个环，使得相邻两个整数之和均为素数。

【输入】

输入正整数nn。

【输出】

输出任意一个满足条件的环。

【输入样例】

6

【输出样例】

4 3 2 5 6 1

【提示】

数据满足：

4≤n≤30

#include<iostream>
#include<cmath>
using namespace std;int n;
bool vis[110];
int cnt[110];
bool flag = false;//先假装搜不到bool isPrime(int x) {if (x < 2) return false;for (int i = 2; i <= sqrt(x); i++) {if (x % i == 0) return false;} return true;
}void dfs(int depth) {//7.终止条件if (depth > n) {//前n层已经搜完了if (!isPrime(cnt[depth - 1] + cnt[1])) return;for (int i = 1; i < depth; i++) {cout << cnt[i] << " ";}cout << endl;flag = true;return;}//1.枚举方案for (int i = 1; i <= n; i++) {//	2.判断标记if ((depth == 1 && !vis[i]) || (depth > 1 && !vis[i] && isPrime(i + cnt[depth - 1]))) {//	3.搜索cnt[depth] = i;//	4.标记 - 防止重复搜索vis[i] = 1;//	5.进入下一层搜索dfs(depth + 1);//	6.回溯vis[i] = 0;if (flag == true) return;}}
}int main() {cin >> n;dfs(1);return 0;
}

优化

#include<iostream>
#include<cmath>
using namespace std;int n;
bool vis[110];
int cnt[110];
bool flag = false;//先假装搜不到//bool isPrime(int x) {
//	if (x < 2) return false;
//	for (int i = 2; i <= sqrt(x); i++) {
//		if (x % i == 0) return false;
//	} return true;
//}bool isPrime[110];//标记素数   isPrime[x]=0/1   0-x是素数  1-x不是素数
//埃氏筛原理：将素数的倍数全部筛掉，留下的就是素数
void E_sieve(int n) {isPrime[0] = isPrime[1] = 1;//0和1不是素数for (int i = 2; i * i <= n; i++) {if (isPrime[i] == 0) {//代表i是素数for (int j = i * i; j <= n; j += i) {//j代表i的所有倍数（n以内）isPrime[j] = 1;//j一定不是素数}}}
}void dfs(int depth) {//7.终止条件if (depth > n) {//前n层已经搜完了if (isPrime[cnt[depth - 1] + cnt[1]]) return;for (int i = 1; i < depth; i++) {printf("%d ", cnt[i]);}cout << endl;flag = true;return;}//1.枚举方案for (int i = 1; i <= n; i++) {//	2.判断标记if ((depth == 1 && !vis[i]) || (depth > 1 && !vis[i] && !isPrime[i + cnt[depth - 1]])) {//	3.搜索cnt[depth] = i;//	4.标记 - 防止重复搜索vis[i] = 1;//	5.进入下一层搜索dfs(depth + 1);//	6.回溯vis[i] = 0;if (flag == true) return;}}
}int main() {cin >> n;E_sieve(2*n);//最大要筛n+n-1,dfs(1);return 0;
}