P1835 素数密度

直接求素数容易超时，反向求合数，再做减法

#include <bits/stdc++.h>
using namespace std;
bool isp[500005]={1,1};
int p[500005],t=0,l,r;
int tong[1000005];
void init(){
    for(int i=2;i<500005;i++){
        if(!isp[i]) p[t++]=i;
        for(int j=0;j<t&&p[j]*i<500005;j++){
            isp[p[j]*i]=1;
            if(i%p[j]==0) break;
        }
    }
}
int main(){
    init();
    cin>>l>>r;
    for(int i=0;i<t;i++){
        if(p[i]>r) break;
        if(p[i]>=l) continue;
        for(long long j=max(2,(l+p[i]-1)/p[i]);j*p[i]<=r;j++)
            tong[j*p[i]-l]++;
    }
    int ans=0;
    for(int i=0;i<=r-l;i++)
        if(tong[i]==0) ans++;
    if(l==1) ans--;
    cout<<ans;
    return 0;
}