当前位置:首页 > 数学 > 筛法 > 正文
SSOJ2899PrimeDistance
34+

题目大意:如何筛出区间内的所有质数?区间大小不超过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.

对于全部数据,1L<R<231,RL106

解题思路

用筛法筛出区间内所有质数,然后打擂台,求出距离最小、最大的相邻质数位置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开始编号了!

程序实现

SSOJ2899PrimeDistance:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter