p1835素数密度，埃氏筛法（大数小区间的素数个数）

线性打表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;
}