首先,筛法一定不行,数组会爆掉
筛法+前缀和版本可以去看洛谷P1865

那么本题要怎么做?
答案:MR素性判断
MR算法可以在k*(logn)^2时间复杂度内判断一个数是不是质数
只需要在l到r区间的i进行MR判断就行了

第一次写题解,而且MR算法需要很多前置知识
本题解可能不适合一点没学的人
AC代码:
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
const int N= +9;
#define T int tcishu=1;cin>>tcishu;while(tcishu--)solve();

int mul(int a, int b, const int mod){
    int d =a*(long double)b/mod;
    int ret =a*b-d*mod;
    if(ret < 0)
        ret +=mod;
    if(ret >= mod)
        ret -=mod;
    return ret;
}

int Pow(int x, int k, const int mod){
    int ret =1;
    for(; k; x =mul(x, x, mod), k >>=1) if(k&1) ret =mul(ret, x, mod);
    return ret;
}

mt19937 engine;

bool mr(int p){
    if(p < 2) return 0;
    if(p == 2) return 1;
    if(p == 3) return 1;
    uniform_int_distribution<int> Rand(2, p-2);
    int d =p-1, r =0;
    while(!(d&1)) ++r, d >>=1;
    for(int k =0; k < 10; ++k){
        int a =Rand(engine);
        int x =Pow(a, d, p);
        if(x == 1 || x == p-1) continue;
        for(int i =0; i < r-1; ++i){
            x =mul(x, x, p);
            if(x == p-1) break;
        }
        if(x != p-1) return 0;
    }
    return 1;
}

signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    srand(time(0));
    int l,r;
    cin>>l>>r;
    int ans=0;
    for(int i=l;i<=r;i++){
        if(mr(i))ans++;
    }
    cout<<ans<<endl;
   
}