天天看点

算法学习之路|POJ2689(素数筛)

题目大意:选出区间L,R之间相邻素数中差值最大和最小的素数对

素数筛(线性筛):

思路:直接用素数筛会超时(int范围线性复杂度时间复杂度已经达到10e9),而区间间隔比较小,只有1e6,而且对于int范围内的合数来说,最小质因子必定小于2^16。所以可以进行二次筛素数,第一次对50000以内筛素数,第二次筛出L,R区间内素数即可。

代码:

继续阅读