莫欺少年穷，修魔之旅在这开始—>算法提高课题解

思路：

1. 如果 n 是合数，那么 n 的最小质因子必小于 sqrt(n)，因此可以先预处理出 1～50000 内的所有质数
2. 对于质数 p，先找到 [l, r] 内的 p 的最小倍数 p0，再用埃氏筛将 p 的倍数筛掉，存的是距离 l 的偏移量
3. 枚举距离 l 的偏移量，再将剩下的质数全部取出
4. 依次枚举比较找出距离最近和距离最远的相邻质数的前一个质数的下标

重要知识：$ [l, r]\ 内\ p\ 的最小倍数：\left\lceil\dfrac{l}{p}\right\rceil=\left\lfloor\dfrac{l+p-1}{p}\right\rfloor$

证明： $当\ p \mid l\ 时，假设\dfrac{l}{p}=x,那么\left\lfloor\dfrac{l+p-1}{p}\right\rfloor=x，故\left\lceil\dfrac{l}{p}\right\rceil=\left\lfloor\dfrac{l+p-1}{p}\right\rfloor$
$\ \ \ \ \ \ \ \ \ \ \ 当\ p\nmid l\ 时，l \bmod p\ge 1,假设\dfrac{l}{p}=x,那么\left\lceil\dfrac{l}{p}\right\rceil=x+1,(l+p-1)\div p=x......p_0\ (p_0\ge p)，则\left\lfloor\dfrac{l+p-1}{p}\right\rfloor=x+1，故\left\lceil\dfrac{l}{p}\right\rceil=\left\lfloor\dfrac{l+p-1}{p}\right\rfloor$
$\ \ \ \ \ \ \ \ \ \ \ 综上，\left\lceil\dfrac{l}{p}\right\rceil=\left\lfloor\dfrac{l+p-1}{p}\right\rfloor$

可参考： 筛质数

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 1000010;

int l,r;
int primes[N],cnt;
bool st[N];

//线性筛，把1～50000内的所有质数都筛出来
void init(int n)
{
    memset(st,0,sizeof st);

    for(int i=2;i<=n;i++)
    {
        if(!st[i]) primes[cnt++]=i;
        for(int j=0;primes[j]<=n/i;j++)
        {
            st[primes[j]*i]=true;
            if(i%primes[j]==0) break;
        }
    }
}

int main()
{
    while(cin>>l>>r)
    {
        init(50000);

        memset(st,0,sizeof st);

        //枚举所有质数，先找到[l,r]内p的最小倍数，再埃氏筛把p的倍数都筛掉，存的是距离l的偏移量
        for(int i=0;i<cnt;i++)
        {
            LL p=primes[i];
            for(LL j=max(p*2,(l+p-1)/p*p);j<=r;j+=p) st[j-l]=true;
        }

        //枚举距离l的偏移量，将[l,r]内的所有质数都筛出来
        cnt=0;
        for(int i=0;i<=r-l;i++)
            if(!st[i]&&i+l>=2)
                primes[cnt++]=i+l;

        if(cnt<2) puts("There are no adjacent primes.");
        else 
        {
            //找出距离最近和距离最远的相邻质数的前一个质数的下标
            int minp=0,maxp=0;
            for(int i=0;i+1<cnt;i++)
            {
                int d=primes[i+1]-primes[i];
                if(d<primes[minp+1]-primes[minp]) minp=i;
                if(d>primes[maxp+1]-primes[maxp]) maxp=i;
            }

            printf("%d,%d are closest, %d,%d are most distant.\n",
            primes[minp],primes[minp+1],primes[maxp],primes[maxp+1]);
        }
    }

    return 0;
}