新增备案网站要关闭吗,用最少的钱做网站,百度关键词排名代发,延吉市住房城乡建设局官方网站sakiko要构造一个长度为 nnn 的排列 ppp #xff0c;使得每一个 pii (1≤i≤n)p_ii\ (1\leq i\leq n)pii (1≤i≤n) 都是质数。
排列的定义为#xff1a;长度为 nnn 的数组#xff0c;其中 1−n1-n1−n 每个数字在数组中各出现一次。
输入描述:
第一行输入一个整数 n(1…sakiko要构造一个长度为 nnn 的排列 ppp 使得每一个 pii (1≤i≤n)p_ii\ (1\leq i\leq n)pii (1≤i≤n) 都是质数。
排列的定义为长度为 nnn 的数组其中 1−n1-n1−n 每个数字在数组中各出现一次。
输入描述:
第一行输入一个整数 n(1≤n≤106)n(1 \leq n \leq 10^6)n(1≤n≤106) 表示数组长度。
输出描述:
输出 nnn 个整数表示答案如果有多种解法则输出任意一种。若无解则输出 -1。
示例1
输入
3
输出
1 3 2
切比雪夫定理对于一个大于1的正整数在(a,2a]内总有一个素数
思路在序列1.2.3...n中对于任意一个子序列若能使其第一个数和最后一个数相加等于一个素数那么这一段的构造为从最后一个数倒着把他们放入构造数组中。
#includebits/stdc.h
using namespace std;
const int N2e610;
int prime[N];
bool isprime[N];
int cnt0;
void eular(int n)//欧拉筛法筛出所有素数
{memset(isprime,true,sizeof(isprime));isprime[1]false;for(int i2;in;i){if(isprime[i])prime[cnt]i;for(int j0;prime[j]*injcnt;j){isprime[i*prime[j]]false;if(i%prime[j]0)break;}}
}
int main()
{int n;cinn;eular(2*n);//欧拉筛int in;int a[n1];while(i1){int minpi1;while(!isprime[minp])minp;//找到大于n的第一个素数int miniminp-i;for(int jmini;ji;j){a[j]minp-j;}//存入数组imini-1;//处理前面未处理的部分}for(int i1;in;i)couta[i] ;//输出
}
