求助欧拉筛
  • 板块学术版
  • 楼主Kirei
  • 当前回复4
  • 已保存回复4
  • 发布时间2022/2/18 15:36
  • 上次更新2023/10/28 08:16:26
查看原帖
求助欧拉筛
143050
Kirei楼主2022/2/18 15:36

把break去掉的复杂度是多少(实际上是由于我忘记写了)?

如下

for(int i=2;i<=n;i++){
        if(!vis[i]) prime[++tot]=i;
        for(int j=1;prime[j]*i<=n&&j<=ans;j++)
        {
            vis[prime[j]*i]=1;
        }
    }

实测复杂度大约×2\times2

2022/2/18 15:36
加载中...