MnZn刚学OI,请问为什么线性筛是 n^2 的?
  • 板块学术版
  • 楼主jiarenmen
  • 当前回复4
  • 已保存回复5
  • 发布时间2024/9/28 13:51
  • 上次更新2024/9/28 14:02:35
查看原帖
MnZn刚学OI,请问为什么线性筛是 n^2 的?
1420572
jiarenmen楼主2024/9/28 13:51

如题,这是我的代码:

明明是两层循环,但是它跑过了 10810^8 的规模。

这份代码不应该是 Θ(n2)\Theta(n^2) 的复杂度吗?

void get(){
    for(int i=2;i<N;i++){
        if(!v[i])prime[++tot]=i;
        for(int j=1;j<=tot&&prime[j]*i<N;j++){
            v[prime[j]*i]=1;
            if(i%prime[j]==0)break;
        }
    }
    return;
}
2024/9/28 13:51
加载中...