题解 | #素数的个数#

用Meissel-Lehmer筛法，时间复杂度为 $O(R^{\frac 2 3} + L^{\frac 2 3})$ ，空间复杂度为 $O(R^{\frac 1 3}+L^{\frac 1 3})$ ，需要注意的是计算 $[L,R]$ 区间内的质数也要包含 $L$ 。

#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
vector<int> primes;
int pi[N];
bool isPrime[N];
void sieve(int n) {
    fill(isPrime, isPrime + n + 1, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i <= n; ++i) {
        if (isPrime[i]) primes.push_back(i);
        int len = primes.size();
        for (int j = 0; j < len && i * primes[j] <= n; ++j) {
            isPrime[i * primes[j]] = false;
            if (i % primes[j] == 0) break;
        }
    }
    for (int i = 1; i <= n; ++i) {
        pi[i] = pi[i - 1] + isPrime[i];
    }
}
LL phi(LL x,int s) {
    if (s == 0) return x;
    if (s == 1) return x - x / 2;
    if (s == 2) return x - x / 2 - x / 3 + x / 6;
    if (x < N && pi[x] <= s) return 1;
    return phi(x, s - 1) - phi(x / primes[s - 1], s - 1);
}
LL meissel_lehmer(LL n) {
    if (n < N)return pi[n];
    int a = meissel_lehmer(pow(n, 1.0 / 4));
    int b = meissel_lehmer(pow(n, 1.0 / 2));
    int c = meissel_lehmer(pow(n, 1.0 / 3));
    LL res = phi(n, a) + (b + a - 2) * (b - a + 1) / 2;
    for (int i = a; i < b; ++i) {
        LL w = n / primes[i];
        int lim = meissel_lehmer(sqrt(w));
        res -= meissel_lehmer(w);
        if (i < c) {
            for (int j = i; j < lim; ++j) {
                res = res - meissel_lehmer(w / primes[j]) + j;
            }
        }
    }
    return res;
}
LL L, R;
signed main() {
    scanf("%lld %lld", &L, &R);
    sieve(N - 1);
    printf("%lld\n",meissel_lehmer(R) - meissel_lehmer(L - 1));
    return 0;
}