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;
}