给定整数a和b，请问区间[a,b)内有多少个素数？

a< b<=10^12

b-a<=10^6

输入 

22 37 

输出 

3 

输入 

22801763489 2280178297 

输出 

1000

【分析】b以内的合数的最小质因数一定不超过sqrt(b)。如果有sqrt(b)以内的素数表的话，就可以把埃式筛法运用在[a,b)上了。也就是说，先分别做好[2,sqrt(b))的表和[a,b)的表，然后从[2,sqrt(b))的表中筛得素数的同时，也将其倍数从[a,b)的表中划去，最后剩下的就是区间[a,b)内的素数了。

1 #include
      
        2 #include
       
         3 using namespace std; 4 typedef long long ll; 5 const ll MAX_N=100050; 6  7 bool is_prime[MAX_N]; 8 bool is_prime_small[MAX_N+1]; 9 10 int segment_sieve(ll a, ll b)11 {12     int x = 0;13     for(int i = 0; (ll)i*i < b; i++) is_prime_small[i]=true;14     for(int i = 0; i < b - a; i++) is_prime[i]=true;15     16     for(int i = 2; (ll)i*i < b; i++)17     {18         if(is_prime_small[i])19         {20             for(int j = 2*i; (ll)j*j < b; j+=i) is_prime_small[j]=false;21             for(ll j=max(2LL,(a+i-1)/i)*i;j
        
         >a>>b;35     segment_sieve(a,b);36     int cnt=0;37     for(int j=0; j