Advertisement
Saleh127

LO 1197

Oct 25th, 2020 (edited)
87
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define test int t; cin>>t; for(int cs=1;cs<=t;cs++)
  5. #define maX 46350
  6. bool marked[maX];
  7. vector<ll>prime;
  8. void sieve()
  9. {
  10. marked[0]=1;
  11. marked[1]=1;
  12. for(ll i=4; i<=maX; i+=2)
  13. {
  14. marked[i]=1;
  15. }
  16. for(ll i=3; i<=maX; i+=2)
  17. {
  18. if(marked[i]==0)
  19. {
  20. for(ll j=i*i; j<=maX; j+=i+i)
  21. {
  22. marked[j]=1;
  23. }
  24. }
  25. }
  26. prime.push_back(2);
  27. for(ll i=3; i<=maX; i+=2)
  28. {
  29. if(marked[i]==0)
  30. {
  31. prime.push_back(i);
  32. }
  33. }
  34. }
  35.  
  36. void segmented_sieve(ll l,ll r)
  37. {
  38. bool mark[r-l+1]= {0};
  39. ll base,cp,i,j,cnt=0;
  40.  
  41. if(l==1) mark[0]=1;
  42. for(i=0; prime[i]*prime[i]<=r; i++)
  43. {
  44. cp=prime[i];
  45. base=cp*cp;
  46. if(base<l)
  47. {
  48. base=((l+cp-1)/cp)*cp;
  49. }
  50. for(j=base; j<=r; j+=cp)
  51. {
  52. mark[j-l]=1;
  53. }
  54. }
  55. for(i=0; i<=r-l; i++)
  56. {
  57. if(mark[i]==0)
  58. {
  59. cnt++;
  60. }
  61. }
  62. cout<<cnt<<endl;
  63. }
  64.  
  65. int main()
  66. {
  67. ios_base::sync_with_stdio(0);
  68. cin.tie(0);
  69. cout.tie(0);
  70.  
  71. sieve();
  72.  
  73. test
  74. {
  75. ll r,l;
  76. cin>>l>>r;
  77. cout<<"Case "<<cs<<": ";
  78. segmented_sieve(l,r);
  79. }
  80.  
  81.  
  82. return 0;
  83. }
  84.  
Advertisement
RAW Paste Data Copied
Advertisement