196. 质数距离

196. 质数距离

素数筛，由于L,R范围过大

没法一次全筛出来，先线性筛筛出1-1e5范围内的素数

然后埃氏筛筛出L,R范围内的质数

能用数组

不要用unordered_map

#include<bits/stdc++.h>
using namespace std;
#define int  long long
#define si signed
#define sc(x) scanf("%lld",&x);
#define maxn 50000+10
int P[maxn];
bool vis[maxn];
bool f[1000000+10];
int tot;
//unordered_map<int,si> mp;
int L,R;
void init()
{
    vis[1]=1;
    for(int i=2; i<maxn; i++)
    {
        if(!vis[i])
        {
            P[tot++]=i;
        }
        for(int j=0; i*P[j]<maxn&&j<tot; j++)
        {
            vis[i*P[j]]=1;
            if(i%P[j]==0)
            {
                break;
            }
        }
    }

}
void work()
{

    for(int i=0; P[i]*P[i]<=R&&i<tot; i++)
    {
        int s=max(P[i],L/P[i]);
       // cout<<i<<endl;
        if(s*P[i]<L)s++;
        for(; s*P[i]<=R; s++)
        {
           // cout<<s<<endl;
            f[s*P[i]-L]=1;
        }
    }

}
si main()
{
    init();

    while(scanf("%lld%lld",&L,&R)!=EOF)
    {

        int ma=0,mi=1e10;
        int a=-1,b=-1,c;
        int c1=-1,c2,d1=-1,d2;
        memset(f,0,sizeof f);

        work();

        for(int i=L; i<=R; i++)
        {

            if(i!=1&&(!f[i-L]))

            {
                if(a==-1)
                {
                    a=i;
                }
                else
                {
                    b=a;
                    a=i;
                    if(a-b>ma)
                    {
                        ma=a-b;
                        d1=b;
                        d2=a;
                    }
                    if(a-b<mi)
                    {
                        mi=a-b;
                        c1=b;
                        c2=a;
                    }
                }
            }

        }
        if(c1==-1)
        {
            puts("There are no adjacent primes.");
        }
        else
        {
            printf("%lld,%lld are closest, %lld,%lld are most distant.\n",c1,c2,d1,d2);
        }
    }
}