说错了，是$\times \log x$
by xzz_cat6 @ 2024-04-18 10:34:21
这个差不多是线性的，达到复杂度下界，所以没有更优的了
by yukimianyan @ 2024-04-18 10:45:18
@[xzz_cat6](/user/773813) https://www.luogu.com.cn/problem/CF622F 有 $\mathcal O(x)$ 的
by Pentiment @ 2024-04-18 11:13:42
@[Run_Time_Error](/user/879904)
搞错了 /kk
by Igallta @ 2024-04-18 11:23:16
@[Iam_God](/user/813622) ~~我还以为有什么高新科技~~
by Pentiment @ 2024-04-18 11:26:57
@[Run_Time_Error](/user/879904)
$\Omicron(\sqrt n \log n)$
咋可能
by Igallta @ 2024-04-18 11:40:57
@[Iam_God](/user/813622) ~~阶乘都能做到 $\mathcal O(\sqrt n\log n)$，这个或许也有可能~~
by Pentiment @ 2024-04-18 11:45:47
@[Run_Time_Error](/user/879904)
你再读读题
by fast_proton @ 2024-04-18 14:19:30
@[xzz_cat6](/user/773813)
有没有可能质数个数就是n/log(n)的
by fast_proton @ 2024-04-18 14:20:06
@[fast_proton](/user/302805) 的确，算了一下，大约为7n，省略常数约为n
by xzz_cat6 @ 2024-04-18 14:58:43