题目描述
给定区间[L，R](L≤R≤2147483647,R-L≤1000000)，请计算区间中素数的个数。
输入输出格式
输入格式：
两个数L和R。
输出格式：
一行，区间中素数的个数。
输入输出样例
输入样例#1：
2 11
输出样例#1：
5
AC代码：
#include<cstdio>
#include<cmath>
using namespace std;
const int N=1e6+;
int ans,l,r,k1,k2,L;//k1,k2是为了以一次除法代替大量乘法运算
bool f,check[N];
int main(){
scanf("%d%d",&l,&r);
L=r-l+;
if(l<) l=;
k1=sqrt(r+0.5);
for(int j,i=;i<=k1;i++){
if(i>=l&&check[i-l]) continue;
k2=r/i;
f=;
for(j=l/i;j<=k2;j++) if(j>){
if(f&&i*j<l){f=;continue;}//f是为了防止i*j-l<0致使数组溢出，只判一次节省时间
check[i*j-l]=;
}
}
for(int i=;i<L;i++) if(!check[i]) ans++;
printf("%d",ans);
return ;
}