Advertisement
Farjana_akter

Untitled

Mar 30th, 2020
122
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.63 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int ll;
  4. #define maxn 1000006
  5. bool mark[1000006+5];
  6. ll isprime[maxn+5],psize=0;
  7.  
  8.  
  9. void sieve()
  10. {
  11. mark[0]=true;
  12. mark[1]=true;
  13. for(ll i=2;i*i<=maxn;i++)
  14. {
  15. if(mark[i]==false)
  16. {
  17. for(ll j=i*i;j<=maxn;j+=i)
  18. mark[j]=true;
  19. }
  20. }
  21.  
  22. for(ll i=2;i<=maxn;i++)
  23. {
  24. if(mark[i]==false)
  25. isprime[psize++]=i;
  26. }
  27. }
  28.  
  29. int main()
  30. {
  31. sieve();
  32. ll t,i,j,k,low,high,a,b,c,d,e,f;
  33. cin>>t;
  34. while(t--)
  35. {
  36. cin>>low>>high;
  37.  
  38. vector<ll>v;
  39. for(i=0;i<=psize;i++)
  40. {
  41. if(isprime[i]>=low && isprime[i]<=high)
  42. {
  43. v.push_back(isprime[i]);
  44. }
  45. if(isprime[i]>high)
  46. break;
  47. }
  48. if(v.size()<2)
  49. {
  50. cout<<"No jumping champion"<<endl;
  51. continue;
  52. }
  53. map<ll,ll>m;
  54. for(i=1;i<v.size();i++)
  55. {
  56. a=v[i]-v[i-1];
  57. m[a]++;
  58. }
  59. vector<pair<ll,ll> >vp;
  60. for(auto i: m)
  61. {
  62. vp.push_back(make_pair(i.second,i.first));
  63. }
  64. sort(vp.rbegin(),vp.rend());
  65.  
  66. if(vp.size()==1)
  67. cout<<"The jumping champion is "<<vp[0].second<<endl;
  68. else if(vp.size()>1)
  69. {
  70. if(vp[0].first>vp[1].first)
  71. cout<<"The jumping champion is "<<vp[0].second<<endl;
  72. else
  73. cout<<"No jumping champion"<<endl;
  74. }
  75. else
  76. cout<<"No jumping champion"<<endl;
  77. }
  78. return 0;
  79. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement