注意根式向下取整

根据 ${}^{[1]}$，在 $x\ge 1$ 且 $\alpha >0,\alpha \ne 1$ 时有 $$\sum _{n\le x}{\sigma }_{\alpha }(n)={\displaystyle \frac{\zeta (\alpha +1)}{\alpha +1}}{x}^{\alpha +1}+O(x^{max\{1,\alpha \}}),$$ 所以 ${\sigma }_{1/2}(n)$ 应该是 $O(\sqrt{n})$ 的。更精细的上界就不知道了（ ${}^{[1]}$: Apostol, Tom M. (1976), Introduction to analytic number theory, Undergraduate Texts in Mathematics, New York-Heidelberg: Springer-Verlag, ISBN 978-0-387-90163-3, MR 0434929, Zbl 0335.10001, p. 60.

设： $$n=\prod _i{p}_i^{e_i}$$ $$f(n)=\sum _{d|n}{d}^{1/2}=\prod _i\frac{p_i^{(e_i+1)/2}-1}{p_i^{1/2}-1}$$ 设 $n$ 为前 $k$ 个质数之积，则： $$f(n)=\prod _{i=1}^k(p_i^{1/2}+1)$$ - 设 $g(n)=f(n)/\sqrt{n}$ - 下面是 $k$ 与 $g(n)$ 的关系： - $k=10,g(n)=19.652466$。 - $k=38,g(n)=377.979437$。 - $k=58,g(n)=1409.553112$。 - 因此可以基本判定 $g(n)=\omega (\sqrt{n})$。 虽然但是，这个复杂度很可能是作者对 $n$ 的每个因数求积性函数导致的，在这种情况下，有显然的 $O(\text{因子分解})$ 的方法。 - 如果是这个问题，我建议作者不应该关注这个问题，而应该提升自己的算法能力。

设： $$n=\prod _i{p}_i^{e_i}$$ $$f(n)=\sum _{d|n}{d}^{1/2}=\prod _i\frac{p_i^{(e_i+1)/2}-1}{p_i^{1/2}-1}$$ 设 $n$ 为前 $k$ 个质数之积，则： $$f(n)=\prod _{i=1}^k(p_i^{1/2}+1)$$ - 设 $g(n)=f(n)/\sqrt{n}$ - 下面是 $k$ 与 $g(n)$ 的关系： - $k=4,g(n)=5.369817$。 - $k=25,g(n)=125.336655$。 - $k=168,g(n)=127804.033107$。 - $k=1229,g(n)=1610696887547.172911$。 - $k=9592,g(n)=840539887651625723218616123392$。 - 因此可以基本判定 $f(n)=\omega (\sqrt{n})$，且 $g(n)\sim O(1{)}^{\sqrt{k}}$。 虽然但是，这个复杂度很可能是作者对 $n$ 的每个因数求积性函数导致的，在这种情况下，有显然的 $O(\text{因子分解})$ 的方法。 - 如果是这个问题，我建议作者不应该关注这个问题，而应该提升自己的算法能力。

考虑到楼主的评论，在这里说明一下：“根式是否向下取整”根本不会影响该函数的渐近复杂度。

而且以上即对最坏复杂度做出分析，因为平均复杂度已经有人分析了（

我的错（尴尬