锐客网

  1. 首页 > 睿知 > it技术 > >

Prime Distance(区间筛)

IT知识primedistance

【Prime Distance(区间筛)】怀抱观古今，寝食展戏谑。这篇文章主要讲述Prime Distance(区间筛)相关的知识，希望能为你提供帮助。


??题目链接??? 题意：输入区间[l,u]，其中l和u为int范围的整数，区间最大为1000000。求出[l,u]中，相邻素数只差最大和最小的素数对。当存在多个时，输出较小的素数对。
思路：
首先看数据量，和是开不出来这个数组，其次O(n)线性筛也筛不出来，再往后看这就为我们区间筛做了很大的准备，通过这个条件我们可以想起来把转化成这样数组最大开出能开出来,内存的问题解决了，我们来看时间：我们筛的素数需要知道的素数，那么我们就可以利用根r中的素数来筛

    推荐阅读


    上一篇：004.maven概念模型图

    下一篇：问题 K: 最勇敢的机器人(并查集＋背包)