关于 S 组阅读程序 T2

就是埃筛 $\sigma(n)$ 的那道题。

我在考场上填的是 $O(n\log \log n)$，但我算的是筛到 $n$ 的情况，实际上原程序只筛到了 $\sqrt n$。

于是有学长说复杂度是 $O(\sqrt n\log \log n+n-\sqrt n)=O(n)$，我认为他说的有道理。

但是洛谷和小图灵都说是 $O(n\log \log n)$，希望得到解释。