G题解 | #签到了签到了#

//筛一遍所有质数 再用二分法查找范围内的质数个数

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;

const int N = 10000010;
vector<int> primes;
bool st[N];

void init()
{
    for(int i = 2; i <= N; i++) {
        if(!st[i]) primes.push_back(i);
        for(int p : primes)
        {
            if(i * p > N) break;
            st[i * p] = true;
            if(i % p == 0) break;
        }
    }
}

int main()
{
    init();
    
    int T;
    
    cin >> T;
    
    while(T--)
    {
        int x, y;
        cin >> x >> y;
        
        //二分法查找第一个大于等于x的数的下标
        //查找第一个小于等于y的数的下标
        int l = 0, r = primes.size() - 1;
        
        while(l < r)
        {
            int mid = l + r >> 1;
            if(primes[mid] >= x) r = mid;
            else l = mid + 1;
        }
        
        int l1 = 0, r1 = primes.size() - 1;
        
        while(l1 < r1)
        {
            int mid = l1 + r1 + 1 >> 1;
            if(primes[mid] <= y) l1 = mid;
            else r1 = mid - 1;
        }
        
        //cout << primes[l1];
        if(primes[l1] > y) cout << l1 - l << endl;
        else if(primes[l] < x) cout << l1 - l << endl;
        else if(primes[l1] > y && primes[l] < x) cout << l1 - l - 1 <<endl;
        else cout << l1 - l + 1 << endl;

    }
    return 0;
}