大区间筛选素数

给定整数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)内的素数了。
【示例代码】

    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    #include<map>
    #include<vector>
    #include<queue>
    #include<stack>
    using namespace std;
    #define LL long long
    
    #define MAX_L 1000007
    #define MAX_SORT_B 1000007
    
    bool is_prime[MAX_L];
    bool is_prime_small[MAX_SORT_B];
    
    //对区间[a,b)内的整数执行筛法。isprime[i - a]=true <=> i是素数
    
    void segment_sieve(LL a,LL b)
    {
        for(int i=0; (LL)i*i < b; i++)is_prime_small[i]=true;
        for(int i=0; i<b-a; i++)is_prime[i]=true;
        for(int i=2; (LL)i * i<b; i++)
        {
            if(is_prime_small[i])
            {
                for(int j=2*i; (LL)j * j < b; j += i)
                {
                    is_prime_small[j]=false;//筛[2,sqrt(b))
                }
                for(LL j=max(2LL, (a+i-1)/i)*i ; j<b; j+=i) //(a+i-1)/i为[a,b)区间内的第一个数至少为i的多少倍.
                {
                    is_prime[j - a] =false;//筛[a,b)
                }
            }
        }
    }
    
    int main()
    {
        long long a,b;
        while(~scanf("%lld %lld",&a,&b))
        {
            segment_sieve(a,b);
            int cnt=0;
            for(int j=0; j<b-a; j++)
            {
                if(is_prime[j])cnt++;
            }
            if(a==1)cnt--;
            printf("%d
",cnt);
        }
        return 0;
    }