# 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.