区间筛

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int const N=1e6+7;
int n,m,cnt;
int v[N],p[N],vis[N];
int main(){
	for(int i=2;i<=1e5;++i){
		if(v[i]==0){
			p[++cnt]=i;
			v[i]=i;
		}
		for(int j=1;j<=cnt&&p[j]*i<=1e5&&p[j]<=v[i];++j){  //i%p[j]!=0
			v[ p[j]*i ]=p[j];
		}
	}
	int l,r;
	cin >> l >> r;
	if(l==1) l++;
	for(int i=1;i<=cnt&&p[i]<=sqrt(r);++i){
		for(ll j=l/p[i];j*p[i]<=r;j++){
			if(j*p[i]<l) j++;
			if(j==1) j++;
			vis[  j*p[i]-l ]=1;
		}
	}
	int ans=0;
	for(int i=0;i<=r-l;++i){
		if(!vis[i]) ans++;
	}
	cout << ans;
	return 0;
}