题解 | 质数统计

这种多区间查询的题都可以试着往容斥方向去想一下，我们可以先求出[1, X]内的质数然后做差就可以了。

为了求[1, X]可以先把1e6内的质数全筛出来再二分。

std::vector<int> minp, primes; // i的最小质因子，素数集合
void sieve(int n) 
{
    minp.assign(n + 1, 0);
    primes.clear();
    
    for (int i = 2; i <= n; i++) 
    {
        if (minp[i] == 0) 
        {
            minp[i] = i;
            primes.push_back(i);
        }
        
        for (auto p : primes) 
        {
            if (i * p > n) 
            {
                break;
            }
            minp[i * p] = p;
            if (p == minp[i]) // 在之前已经被筛了
            {
                break;
            }
        }
    }
}

inline void solve() 
{
    sieve(N);
    int q; cin >> q;

    auto query = [&](int x) -> int
    {

        if (x < 2) return 0;

        int l = 0, r = primes.size() - 1;
        while (l < r)
        {
            int mid = (l + r + 1) / 2;
            if (primes[mid] <= x) l = mid;
            else r = mid - 1;
        }

        return l + 1;
    };

    while (q--)
    {
        int l, r; cin >> l >> r;
        // cout << query(l) << " " << query(r) << endl;
        // exit(0);
        cout << query(r) - query(l - 1) << endl;
    }
}