YZOJ P1800 质数生成器

[NOIP2015四校联训Day8]质数生成器

时间限制:1000MS 内存限制:131072KB

  • 题目描述

生成给定范围内的所有质数。

  • 输入格式

有多组数据。

输入数据第一行是一个整数\(T(T\leq10)\),表示测试数据的组数。

接下来\(T\)行,每行有两整数\(m, n\),表示要求生成质数的范围是\([m, n] (1 \leq m \leq n \leq 10^9, n-m \leq 10^6)\)

  • 输出格式

对于每一组测试数据,输出所有在\([m, n]\)中的质数\(p\),一行一个。

不同测试数据之间用一个空行分隔。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于\(30\%\)的数据,\(m < n \leq 10^3\);

对于\(50\%\)的数据,\(m < n \leq 10^6 且 n-m \leq 10^3\);

对于\(100\%\)的数据,\(m < n \leq 10^9 且 n-m \leq 10^6\);

 

 

 


 

 

 

看到\(m < n \leq 10^9\)直接被吓到了,但其实注意到\(n-m \leq 10^6\)条件,说明我们只要输出最多\(10^6\)个质数,这是可以接受的。

显然我们无法存下所有的数直接判断,因为空间\(sizeof(int) \cdot 10^9 Bytes \approx 3814 MB\)且时间预处理\(O(N\leq10^9)\)这是无法接受的。所以我们考虑先记下前面几个质数,后面的数就用前面的质数来筛就行。

先用线性筛筛出前几个数的质数,比如我筛到\(10^6\)比较保险,对于每次询问的\(m, n\),如果区间\([m, n]\)与\([1, 10^6]\)有交集,可以很开心的输出在\([1, 10^6]\)区间里的质数。

如果区间\([m, n]\)还有超出区间\([1, 10^6]\)的部分,因为其长度最大为\(10^6\)(\(n-m \leq 10^6\)),我们可以开一个\(10^6\)的数组保存当前这个数是否被之前的质数筛过。然后遍历之前我们筛出来的每一个质数,找到这个质数的所有在当前区间\([max(m, 10^6+1), n]\)的所有倍数打上标记,这样循环结束之后再对区间里的数遍历,没有被打上标记的即为质数,输出即可。

程序实现:

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注