Saleh127

UVA 914 jumping prime.cpp

Jun 5th, 2020
177
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.93 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define test int t; cin>>t; while (t--)
  4. #define ll long long int
  5. #define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  6. #define maX 2000000
  7. ll prime[maX];
  8. bool marked[maX];
  9. void sieve()
  10. {
  11. for(ll i=3; i<=maX; i+=2)
  12. {
  13. if(marked[i]==false)
  14. {
  15. for(ll j=i*i; j<=maX; j+=i+i)
  16. {
  17. marked[j]=true;
  18. }
  19. }
  20. }
  21. ll k=1;
  22. prime[0]=2;
  23. for(ll i=3;i<=maX;i+=2)
  24. {
  25. if(marked[i]==false)
  26. {
  27. prime[k]=i;
  28. k++;
  29. }
  30. }
  31. }
  32. int main()
  33. {
  34. fio
  35. sieve();
  36. test
  37. {
  38. ll d,j,k,l,u,fre[200]={0},cnt[200]={0};
  39. cin>>l>>u;
  40. if(l>u) swap(l,u);
  41. if(l==u)
  42. {
  43. printf("No jumping champion\n");
  44. continue;
  45. }
  46. for(ll x=0; x<maX; x++)
  47. {
  48. if(prime[x]>=l)
  49. {
  50. k=x; ///loop start;
  51. break;
  52. }
  53. }
  54. for(ll i=0; i<maX; i++)
  55. {
  56. if(prime[i]>u)
  57. {
  58. j=i-1; ///loop end;
  59. break;
  60. }
  61. if(prime[i]==u)
  62. {
  63. j=i; ///loop end;
  64. break;
  65. }
  66. }
  67. for(ll a=k+1;a<=j;a++)
  68. {
  69. d=prime[a]-prime[a-1];
  70. fre[d]++; ///for frequency;
  71. cnt[d]++; ///for checking same difference;
  72. }
  73. sort(cnt,cnt+200,greater<int>());
  74. if(cnt[0]==cnt[1])
  75. {
  76. printf("No jumping champion\n");
  77. }
  78. else
  79. {
  80. for(ll c=0;c<200;c++)
  81. {
  82. if(fre[c]==cnt[0])
  83. {
  84. printf("The jumping champion is %lld\n",c);
  85. break;
  86. }
  87. }
  88. }
  89. }
  90. return 0;
  91. }
Advertisement
Add Comment
Please, Sign In to add comment