Lightoj 1197 - Help Hanzo

http://lightoj.com/volume_showproblem.php?problem=1197

1. #include <bits/stdc++.h>
2. using namespace std;
3. #define maxx 100005
4. bitset<maxx>vis;
5.  
6. vector<int>prime;
7.  
8. void sieve()
9. {
10.  
11.     int x=maxx/2, y=sqrt(maxx)/2;
12.     for(int i=1;i<=y;i++)
13.     {
14.         if(vis[i])
15.         {
16.             for(int j=(i*(i+1))*2;j<=x;j+=(2*i)+1)
17.                 vis[j]=1;
18.         }
19.     }
20.     prime.pb(2);
21.     for(int i=3;i<maxx;i+=2)
22.         if(vis[i/2]==0)
23.             prime.pb(i);
24. }
25.  
26. int segmented_sieve(int a, int b){
27.     vis=0;
28.     if(b<2) return 0;
29.     if(a<2) a=2;
30.     int xx=sqrt((double)b)+1;
31.     for(ll i=0;i<SZ(prime) && prime[i]<=xx;i++){
32.         ll j=(a/prime[i])*prime[i];
33.         if(j <a) j+=prime[i];
34.         if(j<(ll)(prime[i]+prime[i])) j=prime[i]+prime[i];
35.         for(;j<=b;j+=prime[i])
36.             vis[j-a]=1;
37.     }
38.     int cnt=0;
39.     for(ll i=a;i<=b;i++)
40.         if(vis[i-a]==0) cnt++;
41.     return cnt;
42. }
43.  
44. int main()
45. {
46.  
47.      ///freopen("in.txt","r",stdin);
48.     ///freopen("out.txt","w",stdout);
49.     sieve();
50.     int t;
51.     sf(t);
52.     TEST_CASE(t)
53.     {
54.         ll a,b;
55.         sffl(a,b);
56.         PRINT_CASE;
57.         printf("%d\n",segmented_sieve(a,b));
58.     }
59.     return 0;
60. }