Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long int ll;
- #define MAX 320000
- bool mark[MAX+5];
- vector<ll>isprime;
- void sieve()
- {
- ll i,j;
- mark[0]=true;
- mark[1]=true;
- for(i=2;i*i<=MAX;i++)
- {
- if(mark[i]==false)
- {
- for(j=i*i;j<=MAX;j+=i)
- mark[j]=true;
- }
- }
- for(i=2;i<=MAX;i++)
- if(mark[i]==false)
- isprime.push_back(i);
- }
- void segsieve(ll l,ll r)
- {
- ll prime[r-l+1+5],i,j;
- for(i=0;i<r-l+1;i++)
- prime[i]=false;
- if(l==1)prime[0]=true;
- for(i=0;isprime[i]*isprime[i]<=r;i++)
- {
- ll curprime=isprime[i];
- ll base=(l/curprime)*curprime;
- if(base<l)
- base+=curprime;
- for(j=base;j<=r;j+=curprime)
- {
- prime[j-l]=true;
- }
- if(base==curprime)
- prime[base-l]=false;
- }
- vector<ll>v;
- for(i=0;i<r-l+1;i++){
- if(prime[i]==false){
- v.push_back(i+l);
- }
- }
- ll mn=1e10,mx=0,c1,c2,d1,d2;
- for(i=1;i<v.size();i++)
- {
- ll diff=v[i]-v[i-1];
- if(diff>mx)
- {
- mx=diff;
- d1=v[i-1];
- d2=v[i];
- }
- if(diff<mn)
- {
- mn=diff;
- c1=v[i-1];
- c2=v[i];
- }
- }
- if(mx==0 || mn==1e10)
- cout<<"There are no adjacent primes."<<endl;
- else
- cout<<c1<<","<<c2<<" are closest, "<<d1<<","<<d2<<" are most distant."<<endl;
- }
- int main()
- {
- sieve();
- ll t,i,j,k,l,r;
- while(cin>>l>>r)
- {
- segsieve(l,r);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement