洛谷P1835素数密度

Question

为什么划线那里要这么写，不管2可不可以?想了半天不明白，但是一输10000 20000就输出0了?

Answer 1

#include <bits/stdc++.h>
using namespace std;
int l,r,now=1;
int prime[50000],isprime[50010];
void build(){
    isprime[1]=0;
    for(int i=2;i<50000;i++){
        if(isprime[i]){
            prime[now++]=i;
        }
        for(int j=1;j<=now&&i*prime[j]<50000;j++){
            isprime[i*prime[j]]=0;
            if(i%prime[j]==0) break;
        }
    }
}
int res[1000010],ans=0;
int main(){
    cin>>l>>r;
    memset(isprime,1,sizeof(isprime));
    build();
    memset(res,1,sizeof(res));
    for(int i=1;i<now&&prime[i]<=r;i++){
        for(long j=max(2,(l-1)/prime[i]+1);j*prime[i]<=(long)r;j++){
            res[j*prime[i]-l]=0;
        }
    }
    if(l<=1) res[1-l]=0;
    for(int i=0;i<=r-l;i++){
        if(res[i]) ans++;
    }
    cout<<ans;
    return 0;
}