p1835素数密度，埃氏筛法（大数小区间的素数个数）
这个是大数（1e9）的小区间（1e6）的素数个数
埃氏n ln n大约2e7 预测400ms
线性打表2~根号n for i：素数表 for j:l~r中i最小的倍数~n st[j]=true for 找出素数代码：
#include <bits/stdc++.h>
using namespace std;
const int N=1e5,M=1e6+7;
int prime[N+5],cnt;
bool st[N+5];
int l,r,ans;
bool isprime[M+5];
void mTable(){
for(int i=2;i<=N;i++){
if(!st[i]) prime[cnt++]=i;
for(int j=0;prime[j]<=N/i;j++){
st[i*prime[j]]=true;
if(i%prime[j]==0) break;
}
}
}
int main(int argc, char** argv) {
cin>>l>>r;
mTable();
for(int i=0;i<cnt;i++){
int p=prime[i];
for(long long j=max((long long)p<<1,1LL*(long long)ceil(1.0*l/p)*p);j<=r;j+=p){
isprime[j-l]=true;
}
}
for(int i=0;i<=r-l;i++)
if(!isprime[i]&&i+l>1) ans++;//注意以上埃氏不能筛1
cout<<ans<<endl;
return 0;
} 
