学步园

题意：给定区间[L,U]，求区间的两对素数，分别是距离最小和距离最大的。这里距离就是两个数的差值

思路：预处理筛选出sqrt(2,147,483,647)以内的素数，然后去筛选出[L,U]的合数，最后从[L,U]的素数中扫描答案

这里用int溢出了。坑。。。

code:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <iomanip>
#include <queue>
#include <vector>
#include <set>
#include <map>
typedef long long LL;
#define inf 0x3f3f3f3f
#define P system("pause")
using namespace std;
#define M 50000
int pri[M],psize;
int nop[M],isnp[1000005];
LL ans[80000];
LL le,ri;
void sieve()
{
    memset(nop,0,sizeof(nop));
    psize=0;
    for(int i=2;i<M;i++)
    {
        if(!nop[i])
        {
            pri[psize++]=i;
            for(int j=i+i;j<M;j+=i)
                nop[j]=1;
        }
    }
}
void make()
{
    memset(isnp,0,sizeof(isnp));
    for(LL i=0;i<psize&&pri[i]*pri[i]<=ri;i++)
    {
        LL t=le/pri[i];
        while(t*pri[i]<le||t<=1)t++;
        for(LL j=t*pri[i];j<=ri;j+=pri[i])
        {
            if(j-le>=0)isnp[j-le]=1;
        }

    }
    if(le==1)
        isnp[0]=1;
}
void solve()
{
    LL maxi,mini,mina,minb,maxa,maxb;
    int yes=0;
    maxi=-inf;
    mini=inf;
    make();
    for(int i=0;i<=ri-le;i++)
    {
        if(isnp[i]==0)
        {
            ans[yes++]=i+le;
        }
    }
    if(yes<2)
        puts("There are no adjacent primes.");
    else
    {
        for(int i=0;i<yes-1;i++)
        {
            if(ans[i+1]-ans[i]<mini)
            {
                mini=ans[i+1]-ans[i];
                mina=ans[i];
                minb=ans[i+1];
            }
            if(ans[i+1]-ans[i]>maxi)
            {
                maxi=ans[i+1]-ans[i];
                maxa=ans[i];
                maxb=ans[i+1];
            }
        }
        printf("%lld,%lld are closest, %lld,%lld are most distant.\n",mina,minb,maxa,maxb);
    }
}
int main()
{
    sieve();
    while(scanf("%lld%lld",&le,&ri)!=EOF)
    {
        solve();
    }
    return 0;
}