快速筛一个区间的质数（l或r很大但区间长度比较小）

受以前做过一道题的启发，其实筛质数的同时也是筛合数

判断一个数是否为合数，就要判断这个数是否有除1和自身以外的因子，换句话说，判断该数是否为除1和自身以外的数的倍数

为什么要换句话呢？因为传统的判断一个数是否为合数（质数）的方法是从2到√n枚举每个数，然后用取余是否为0的方法来加以区别，如果一个数为质数，就会把2到√n整个区间扫一遍，也就是√n的复杂度

但是对于一个区间来说，判断每个数都是√n（最坏情况），区间长度为m，那么总共就是m√n，这显然是不太友好的

既然筛质数会到达最坏情况，那么我们为什么不筛合数来避免这种情况呢

刚才说了，判断一个数是否为合数，就看它是不是其他数的倍数（除1和自身），但是我们不用除法，而是用加法（乘法）

枚举每一个因子，看他的倍数是否在区间内，如果在，那么该数为区间内的合数

而依次增加倍数的过程，其实也就是一个加法的过程，每次加上该因子，就相当于多了一倍，并且加法也比乘法快

现在来分析一下时间复杂度，为什么这么做是可行的？

我们枚举每一个因子（以下统称x），是从2到√区间右端点（若区间为（l，r），那么为√r），这样每一个因子都不会漏掉

而逐次增加倍数的过程呢，r除以x即为增加的次数，超过区间直接退出就好，也就是说时间复杂度为√r*（r/x），基本上相当于 r的复杂度，对于该题而言这当然也不可取（r最大为1e9），我们需要做一些优化

对于区间外的数，我们并不关心它是否为合数（质数），所以枚举的倍数不是从2开始，而是从l（左端点）/x开始，这么处理就可以让倍数最快达到区间内，然后依次筛出区间内x的倍数（也就是合数）

如此处理后，增加的次数就变成了m（区间长度）/x,如此一来时间复杂度就变为√r*（m/x）,平均下来差不多就是m的复杂度了（实际上要多一点），这样的处理的话时间复杂度就可以接受了，接下来说一些细节

枚举倍数的起点的时候，最少要从2x开始，因为x单独一个数不能判断是不是合数，所以取起点的时候就取（2x，l/x*x）的最大值就好了，然后就要把增加倍数的过程中增加到的数都要标记一下（合数），虽然l和r很大但是区间长度不大，映射一下就好了，具体可以用哈希来实现，我是直接把区间映射到从1到n

筛完合数，没被标记的就是质数了，剩下的就简单了，完工！

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long long ll;

const int N = 1e6 + 10;

bool st[N];
ll n, m, l, r, p, q;
ll ans, res, pre;

int main()
{
    while(scanf("%lld%lld", &n, &m), n && m)
    {
        p = sqrt(m);
        for(int i = 1; i <= m - n + 1; ++ i) st[i] = 0;
        if(n == 1) st[1] = 1;
        for(int i = 2; i <= p; ++ i)
        {
            q = max(2ll, n / i) * i;
            while(q <= m)
            {
                if(q >= n) st[q - n + 1] = 1;
                q += i;
            }
        }

        ans = N;
        pre = res = 0;
        for(int i = 1; i <= m - n + 1; ++ i)
            if(!st[i])
            {
                if(pre)
                {
                    if(i - pre < ans)
                    {
                        l = pre;
                        ans = i - pre;
                    }
                    if(i - pre > res)
                    {
                        r = pre;
                        res = i - pre;
                    }
                }
                pre = i;
            }

        l += n - 1;
        r += n - 1;
        if(res) printf("%lld,%lld are closest, %lld,%lld are most distant.\n", l, l + ans, r, r + res);
        else puts("There are no adjacent primes.");

        n = m = 0;
    }

    return 0;
}