求一个正整数N的因子个数或该正整数N的所有因子之和

如果要求一个正整数N的因子个数,只需要对其质因子分解,得到各质因子$P_i$的个数分别为$e_1$、$e_2、...、e_k$,于是N的因子个数就是$(e_1+1)*(e_2+1)*...*(e_k+1)$。原因是对每个质因子$P_i$都可以选择其出现$0$次、$1$次、...、$e_i$,共$e_i+1$种可能,组合起来就是答案。而由同样的原理可知,N的所有因子之和为


$egin{equation}egin{split}
&(1+{P_1}+{P_1}^2+ldots+{P_1}^{e_1})*(1+{P_2}+{P_2}^2+ldots+{P_2}^{e_2})*ldots*(1+{P_k}+{P_k}^2+ldots+{P_k}^{e_k})\
&={frac{1-{P_1}^{e_1+1}}{1-P_1}}*{frac{1-{P_2}^{e_2+1}}{1-P_2}}*ldots*{frac{1-{P_k}^{e_k+1}}{1-P_k}}\
end{split}end{equation}$

原文地址:https://www.cnblogs.com/kachunyippp/p/10256483.html