最差情况是 $O(\frac{n^2}{\log n})$，但是显然跑不满。
by lsj2009 @ 2023-01-03 17:44:34
呸，我是傻逼，最差情况是 $O(\frac{n^3}{\log^2 n})$，但是跑不满。
by lsj2009 @ 2023-01-03 17:48:43
补充一下怎么分析：
由素数定理可知，$n$ 以下的素数有 $O\left(\dfrac n{\ln n}\right)$ 个，所以对于每个数最坏需要 $O\left(\dfrac{n^2}{\ln^2n}\right)$ 的时间解决，而有 $O(n)$ 个数需要解决，所以时间复杂度为 $O\left(\dfrac{n^3}{\ln^2n}\right)$
by cancan123456 @ 2023-01-03 18:20:25
@[cancan123456](/user/448887) 懂了,谢谢
by 跟你沟通 @ 2023-01-03 21:36:25