C - 素数密度

#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
//如果一个数n不是质数，就一定有非一的因数x<=sqrt(n); 
const int N=5e4; //因为所给题目最大到（1<<31） 所以只需要求出来 1~N之间的所有质数就行 
const int M=1e6+7;
int idx=0;
bool prime[N]; 
int p[N], tot;
int ma[M]; //离散化标记 L~R的合数  
void init(){//欧拉筛 
;
    for(int i = 2; i < N; i ++) prime[i] = true;//w++;
    for(int i = 2; i < N; i++){
        if(prime[i]) p[tot ++] = i;
        for(int j = 0; j < tot && i * p[j] < N; j++){
            prime[i * p[j]] = false;// w++;
            if(i % p[j] == 0) break; //w++;
        }
    }
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	init();
	int  ans=0;
	int  l,r,w;
	ma[1]=1; //1 特殊标记 
	cin>>l>>r;
	for(int j=0;j<tot&&p[j]<=sqrt(r);j++) //枚举1~N之间的所有质数 
	{
		 w=(p[j]-l%p[j])%p[j];  //这里的w表示(l+w)%p[j]==0； 
		 if(l+w==p[j])// 这里是l+w刚好等于p[j] ,一倍为质数 
		 w+=p[j]; //所以加一倍 ，为二倍的合数 
		for(long long  i=l+w;i<=r;i+=p[j]) //l+w表示质数p[j]的二倍 ，每次增加一倍 ，把L~R之间所有的p[j] 的倍数标记 
		{
			ma[i%M]=1; //因为所给区间最多为1e6，且递增每次加一，所以modM离散化后，一一对应不会重复 
		}
	}
	for(LL i=l;i<=r;i++) //一一枚举就行 ,这里i开long long ,防止 r=1<<31时 ，再i++ 爆int  
	{
		if(ma[i%M]==0)
		{
			ans++;
		} 
	}
	cout<<ans<<endl;
	return 0;
 }