题解

知识点！！！

线性筛（)
维护布尔型数组 isPrime 储存每个数是否为质数

前缀和（可以不用）
维护整型数组 pre，i 项储存前 i 个数字中有几个质数

两个算法加起来时间复杂度 O(n)，9ms过

代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double dou;
typedef string str;

const int N = 2e6 + 10;

ll l, r;
ll pre[N];
vector<bool> isPrime(N, 1);

void init(ll n)
{
    //0和1不是质数
    isPrime[0] = isPrime[1] = 0;
    //只处理2以上的数
    if (n < 2)
        return;
    vector<int> primes;//储存质数
    
    //线性筛法
    for (int i = 2; i <= n; i++)
    {
        if (isPrime[i] == 1)
            primes.push_back(i);
        for (int j = 0; j < primes.size() && i * primes[j] <= n; j++)
        {
            isPrime[i * primes[j]] = 0;
            if (i % primes[j] == 0)
                break;
        }
    }

    //维护前缀和数组
    for (int i = 1; i <= n; i++)
    {
        pre[i] = pre[i - 1];
        if (isPrime[i])
            pre[i]++;
    }
}

int main()
{
    cin >> l >> r;
    init(r);
    cout << pre[r] - pre[l - 1];
    return 0;
}