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]\)的所有倍数打上标记，这样循环结束之后再对区间里的数遍历，没有被打上标记的即为质数，输出即可。

程序实现：