质因数算法

约数和公式

$\alpha (n)=(1+p_1+p_1^2+\cdots +p_1^{e^1})\ast (1+p_2)\ast \cdots \ast （1+p_k+p_k^2+\dots ）$
其中 $p_i\mathrm{是}n\mathrm{的}\mathrm{质}\mathrm{因}\mathrm{数}$, $e_i\mathrm{是}{p}_i\mathrm{的}\mathrm{指}\mathrm{数}$

约数个数公式

如果 $n$ 可以表示为 $p_1^{e_1}\times p_2^{e_2}\times \cdots \times p_k^{e_k}$
其中 $p_i$ 是质数因数 $e_i$ 是质因数出现的次数那么约数个数就是 $(e_1+1)\times (e_2+1)\times \cdots \times (e_k+1)$

具体细节

使用埃氏筛求出范围内 （$\sqrt{n}$）的质数因为当范围大于 $\sqrt{n}$ 时只有最多只有一个质因数就是他本身