SSOJ2899PrimeDistance
958+
作者：crxis 发布：2021-01-06 分类：筛法
题目大意：如何筛出区间内的所有质数？区间大小不超过100万，端点int范围！
题目描述
原题来自：Waterloo local，题面详见 POJ 2689
给定两个整数 L,R，求闭区间 /span>L,R 中相邻两个质数差值最小的数对与差值最大的数对。当存在多个时，输出靠前的素数对。
输入
多组数据。每行两个数 L,R。
输出
详见输出样例。
提示
样例输入
2 17
14 17样例输出
2,3 are closest, 7,11 are most distant.
There are no adjacent primes.对于全部数据，1≤L<R<231,R−L≤106。
解题思路
用筛法筛出区间内所有质数，然后打擂台，求出距离最小、最大的相邻质数位置j和k，输出第j-1、j个质数和低k-1、k个质数即可。
如何筛出区间内质数？
首先，合数能进行质因数分解，一个不超过根号，一个不小于根号。要筛出int范围内的合数，所需要的质数不需要超过10万！因此，我们可以先预处理出10万以内的质数，保存到p数组。
然后，我们用这些质数进行翻倍，只是不从2倍开始。因为区间是[l, r]，如果质数是x，那么至少从l/x开始，至多到r/x结束，其他数据显然不在范围内。范围不超过100万，那么就跟筛出100万以内的质数的复杂度一样。
注意，l/x需要向上取整，如果用int的话，不能写成(l+x-1)/x，因为会爆int；另外至少从两倍开始筛，不能把质数自己给筛掉了。
最后，标记质数的时候，需要进行哈希，可以用直接定址法，因为数据连续，只需要大家都减去l-1，就可以从1开始编号了！
程序实现
