vps做网站怎么加速seo推广灰色词
信息学奥赛一本通（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;
}