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 maxn 1000006
- bool mark[1000006+5];
- ll isprime[maxn+5],psize=0;
- void sieve()
- {
- mark[0]=true;
- mark[1]=true;
- for(ll i=2;i*i<=maxn;i++)
- {
- if(mark[i]==false)
- {
- for(ll j=i*i;j<=maxn;j+=i)
- mark[j]=true;
- }
- }
- for(ll i=2;i<=maxn;i++)
- {
- if(mark[i]==false)
- isprime[psize++]=i;
- }
- }
- int main()
- {
- sieve();
- ll t,i,j,k,low,high,a,b,c,d,e,f;
- cin>>t;
- while(t--)
- {
- cin>>low>>high;
- vector<ll>v;
- for(i=0;i<=psize;i++)
- {
- if(isprime[i]>=low && isprime[i]<=high)
- {
- v.push_back(isprime[i]);
- }
- if(isprime[i]>high)
- break;
- }
- if(v.size()<2)
- {
- cout<<"No jumping champion"<<endl;
- continue;
- }
- map<ll,ll>m;
- for(i=1;i<v.size();i++)
- {
- a=v[i]-v[i-1];
- m[a]++;
- }
- vector<pair<ll,ll> >vp;
- for(auto i: m)
- {
- vp.push_back(make_pair(i.second,i.first));
- }
- sort(vp.rbegin(),vp.rend());
- if(vp.size()==1)
- cout<<"The jumping champion is "<<vp[0].second<<endl;
- else if(vp.size()>1)
- {
- if(vp[0].first>vp[1].first)
- cout<<"The jumping champion is "<<vp[0].second<<endl;
- else
- cout<<"No jumping champion"<<endl;
- }
- else
- cout<<"No jumping champion"<<endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement