Eratosthenes 筛时间复杂度求助
  • 板块灌水区
  • 楼主Alea
  • 当前回复5
  • 已保存回复5
  • 发布时间2023/10/2 14:52
  • 上次更新2023/11/2 16:34:18
查看原帖
Eratosthenes 筛时间复杂度求助
322792
Alea楼主2023/10/2 14:52
const int range=1e6;
bool isprime[range+10];
void eratosthenes(){
    memset(isprime,1,sizeof(isprime));
    isprime[0]=isprime[1]=false;
    for(int i=2;i*i<=range;i++){
        if(isprime[i]) for(int j=2;j*i<=range;j++) isprime[i*j]=false;
    }
    return;
}

请问这段代码的时间复杂度可否达到 O(ln⁡ln⁡nn)\mathrm O(\ln\ln n\sqrt{n})

2023/10/2 14:52
加载中...