这个数据范围本身就让这么做啊
by 王熙文 @ 2022-10-24 21:30:41
@[王熙文](/user/353688) 但是 $O(nlogn)$ 会超吧
by YuRuochen @ 2022-10-24 21:32:00
这个是 loglog 吧
by jijidawang @ 2022-10-24 21:32:47
@[YuRuochen](/user/658786) 埃氏筛是 $O(n\log\log n)$ 的吧
by liqingyang @ 2022-10-24 21:32:59
srds，这样直接用 $\sum\limits_{p}\frac{n}{p}$ 的复杂度求欧拉函数值的复杂度是什么级别的啊/yun
by donghanwen1225 @ 2022-10-24 21:36:45
埃氏筛 loglog n 的，经常用来爆艹线性筛相关的东西感觉，比如去年 NOIP T1 /kx
by Illusory_dimes @ 2022-10-24 21:37:19
@[donghanwen1225](/user/153687) 大体当成 n log 就行了
by Illusory_dimes @ 2022-10-24 21:38:56
@[donghanwen1225](/user/153687) 埃氏筛不就是 $\sum_p \frac{n}{p}$ 的吗？
by liqingyang @ 2022-10-24 21:39:24
。。。。
by S00021 @ 2022-10-24 21:39:52
@[liqingyang](/user/272088) 哦确实，没想到这一点（（
by donghanwen1225 @ 2022-10-24 21:48:44