略小于 $\sqrt{n}$ ，$n=10^9$ 的时候大概 $1300$ ，$n = 10^{18}$ 的时候大概 $100000$ 。（求个更紧的界？
by zhoutb2333 @ 2019-06-01 11:25:05
@[zhoutb2333](/space/show?uid=31564) 好的谢谢。这个怎么证明啊？
by Gypsophila @ 2019-06-01 11:27:25
证明 $< 2 \sqrt{n}$ ：$< \sqrt{n}$ 的约数最多有 $\sqrt{n}$ 个， $> \sqrt{n}$ 的约数都对应一个小的约数，也最多有 $\sqrt{n}$ 个
[证明 $n > 1260$ 时候约数个数严格小于 $\sqrt{n}$ 的论文 ](https://wenku.baidu.com/view/9e336795bb4cf7ec4afed057.html)
by zhoutb2333 @ 2019-06-01 11:31:47
@[zhoutb2333](/space/show?uid=31564) 好的谢谢
by Gypsophila @ 2019-06-01 11:35:59
前缀和是$O(n\log n)$的，单个$O(\sqrt{n})$并且实际上还要小很多
by qwaszx @ 2019-06-01 11:36:57
by ButterflyDew @ 2019-06-01 11:58:36
神……神仙讨论
by tiger0133 @ 2019-06-01 12:18:08