题目地址
基本思路：
将区间内质数离散化到空间大小为1e6的数组中.
易错点：
需要特判l==1和l/primes[i]>1的情况.
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
const int MAXN=1000001,INF=2147483647;
int primes[MAXN];
bool notPrime[MAXN];
int primeCnt=0;
void initPrime(){
for(int i=2;i<=sqrt(INF);i++){
if(notPrime[i])continue;
primes[++primeCnt]=i;
for(int j=2;j<=sqrt(INF)/i;j++){
notPrime[i*j]=1;
}
}
}
int newPrimes[MAXN];
int main(){
initPrime();
int l,r;
scanf("%d%d",&l,&r);
if(l==1)notPrime[0]=1;
for(int i=1;i<=primeCnt;i++){
for(int j=l/primes[i];j<=r/primes[i];j++){
if(j>1)notPrime[primes[i]*j-l]=1;
}
}
int newPrimeCnt=0;
for(int i=l;i<=r;i++){
if(!notPrime[i-l])newPrimes[++newPrimeCnt]=i;
if(i==r)break;
}
printf("%d\n",newPrimeCnt);
return 0;
}
