题目

给定区间[L,R]（1≤L≤R<，R−L≤），请计算区间中素数的个数。

输入输出格式

输入格式

第一行，两个正整数L和R。

输出格式

一行，一个整数，表示区间中素数的个数。

输入输出样例

输入样例

2 11

输出样例

5

解析

针对这个题目，R-L的范围比较正常，理论上只要不超过的质数就可以筛除题目范围内的所有合数。

事实上，再联系到的筛选流程，一个区间筛的算法大致成型：预先求出50000以内的所有质数（发现只有不到6000个），再对每个质数进行一遍[L,R]上的合数筛选。最后统计一下没被筛过的就是质数了。

因为只需要利用a[L……R]的数，所以代码中将这段区间平移到了a[0……R-L]，是一个省空间的好方法。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 1000010
int n,N,x,pri[10000];
bool a[maxn];\
int Eratosthenes_Sieve(int n,int pri[]){
	for(int i=2;i*i<=n;i++){
		if(a[i]==0){
			for(int j=i<<1;j<=n;j+=i){
				a[j]=1;
			}
		}
	}
	int cnt=0;
	for(int i=2;i<=n;i++){
		if(!a[i]){
			pri[cnt++]=i;
		}
	}
	return cnt;
}
int main(){
	int cnt=Eratosthenes_Sieve(50000,pri);
	long long l,r;
	scanf("%lld%lld",&l,&r);
	l=l==1?2:l;
	memset(a,0,sizeof(a));
	for(int i=0;i<cnt;i++){
		for(long long j=max(2ll,(l-1)/pri[i]+1)*pri[i];j<=r;j+=pr[i]){
			a[j-l]=1;
		}
	}
	int ans=0;
	for(long long i=l;i<=r;i++){
		if(a[i-l]==0){
			ans++;
		}
	}
	printf("%d",ans);
	return 0;
}