質數距離

題目:

題解:

轉化為篩出區間内的質數

因為對于每一個數,都存在一個小于等于的約數

首先求出 ,是以首先篩出以内的素數,

#include <bits/stdc++.h>
using namespace std;
long long pri[1000005];
long long st[1000005];
long long primes[1000005];
int con;
void prime()
{
     for(int i=1;i<=50005;i++) pri[i]=1;
     pri[1]=0;
     for(int i=2;i<=50005;i++)
     {
         if(pri[i])
         {
             primes[++con]=i;
             for(int j=2;j*i<=50005;j++)
             {
                 pri[j*i]=0;
             }
         }
     }
}
int main()
{
    long long l,r;
    while(cin>>l>>r)
    {
        prime();
        memset(st,0,sizeof(st));
        for(int i=1;i<=con;i++)
        {
            long long p=primes[i];
            for(long long j=max(p*2,(p+l-1)/p*p);j<=r;j+=p)
            {
                st[j-l]=1;
            }
        }
        int c=0;
        long long cha=r-l;
        //cout<<cha<<endl;
        for(long long i=0;i<=cha;i++)
        {
            if(!st[i]&&i+l>=2) primes[++c]=i+l;
            //cout<<c<<endl;
        }
        //cout<<c<<endl;
        if(c<2) cout<<"There are no adjacent primes."<<endl;
        else 
        {
            long long ma=-1,mi=1e12;
            long long a1,a2;
            for(long long i=1;i<=c-1;i++)
            {
                long long d=primes[i+1]-primes[i];
                if(d>ma) 
                {
                    ma=d;
                    a1=i;
                }
                if(d<mi)
                {
                    mi=d;
                    a2=i;
                }
            }
            cout<<primes[a2]<<","<<primes[a2+1]<<" are closest, ";
            cout<<primes[a1]<<","<<primes[a1+1]<<" are most distant."<<endl;
        }
    }
    return 0;
}