#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 50000;
int n, m, k, L, R, ans, vis[N], f[1000005];
int main(){
	cin >> L >> R;
	if (L == 1) ++L; // 特判L=1的情况
	if (L > R){
		cout << 0;
		return 0;
	}
	for (int i = 2; i <= sqrt(R); ++i){
		if (vis[i])
			continue;
		for (int j = i + i; j <= sqrt(R); j += i)
			vis[j] = 1;  // 筛质数
		ll p = ((L - 1) / i + 1) * i; // p是[L,R]中最小的能被质数i整除的数
		if (p == i) p += i; // 如果p=i,那么p不能被筛掉，让p+=i
		for (ll j = p; j <= R; j += i) // 从L~R中把i的倍数筛掉
			f[j - L] = 1;
	}
	for (int i = 0; i <= R - L; ++i)
		if (!f[i]) ++ans;
	cout << ans;
}

这样例多少有点问题，提交AC了样例输出0

暴力枚举 $L$ ~ $R$ 时间复杂度为$O((R-L)\sqrt{R-L})$，无法通过。如果直接筛的话 $L$ 和 $R$ 又太大，会超时。

但 $R-L$ 没那么大，我们可以由 $2$ 筛到 $\sqrt{R}$，这样时间复杂度为 $O((R-L)\log (R-L))$，可以通过了。

实现时下标需要使用 $0$~$10^6$ 来代替 $L$~$R$，不然空间会爆。

AC code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1e6+5,M=50000; // sqrt(r)<50000
ll l,r,ans;
bool vis[M],f[N]; // vis的范围是2~sqrt(r)，f是l~r映射到0~1e6的数组
int main(){
    scanf("%lld%lld",&l,&r);
    l=l==1?1ll*2:l; // 注意特判l=1的情况
    for(ll i=2;i*i<=r;i++)
        if(!vis[i]){
            for(ll j=i+i;j*j<=r;j+=i) // 筛
                vis[j]=1;
            ll p=((l-1)/i+1)*i; // 找出第一个大于等于l的i的倍数
            p=p==i?p+i:p; // 特判p==i的情况，如果为true需要将p+=i，因为i不能被筛掉
            for(ll j=p;j<=r;j+=i)
                f[j-l]=1; // 将j减去l映射
        }
    for(ll i=0;i<=r-l;i++) // 统计素数个数
        if(!f[i])
            ans++;
    printf("%lld",ans);
    return 0;
}