codeforces Hungry Sequence

本文从WordPress迁移而来, 查看全部WordPress迁移文章

http://codeforces.com/contest/327/problem/B

素数,构造,简单题

题意:一个长度为n的严格递增的序列,要求任意两个数都不能有整除关系,让你构造一个这样的序列。序列长度上限为10^5,其实序列 的每个数字的大小上限为10^7

策略:任意两个数不能满足整除关系,很容易想到,要不就干脆构造一个素数序列吧,肯定不会满足整除关系。

筛选出10^7以内的所有素数,有664579个,已经超过了10^5,所以我们不需要这么多的素数

直接读出第10^5个素数,是1299709,所以筛素数的上限设为这么多即可

根据n的大小,一直筛,一直打印,知道打印到第n个素数就停止,结束

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 1299709

bool vis[N];
int prime[N],p,n;

void init(){
p = 0;
memset(vis,false,sizeof(vis));
for(int i = 2; i <= N; i++)
if(!vis[i]){
p++;
for(int j = i + i; j <= N; j += i)
vis[j] = true;
if(p < n) printf("%d ",i);
else{
printf("%d\n",i);
return ;
}
}
}

int main(){
cin >> n;
init();
return 0;
}