求一个正整数所有正因数的和

本文主要是介绍求一个正整数所有正因数的和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

---

前言

一段时间里不知道要写什么好，遇不见适合分享的东西，也懒了一点儿。本篇是关于求正整数正因数和的，另外有一些类似的引申。

---

一、普通的眼光

首先，一个正整数可以根据素因式分解唯一定理得到一个唯一的素数乘积的表示形式：

$a=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\dots p_m^{{\alpha }_m}$

于是它的任意一个因式可以表示为：

$p_1^{{\beta }_1}{p}_2^{{\beta }_2}\dots p_m^{{\beta }_m}$

其中${\alpha }_i$和${\beta }_i$满足${\alpha }_i\ge {\beta }_i$。
然后我们考虑一个式子：

$(1+p_1+p_1^2+\cdots +p_1^{{\alpha }_1})(1+p_2+p_2^2+\cdots +p_2^{{\alpha }_2})\dots (1+p_m+p_m^2+\cdots +p_m^{{\alpha }_m})$

把这个式子乘开后每一项都是$a$的一个因数，如果我们能说明这些因数涵盖了$a$的所有因数并且没有重复就可以说明这个式子的结果与$a$的所有正因数和相等。

1.涵盖

只需要注意到对于任意的$p_1^{{\beta }_1}{p}_2^{{\beta }_2}\dots p_m^{{\beta }_m}$，对应于乘积式里每个素数对应次幂的项的乘积。

1.不重复

根据素因式分解唯一定理即知，每一个因数只有一种分解，只对应于唯一一个项，如果有两个项对应的数字相同则与素因式分解唯一定理矛盾。

二、奇葩的眼光

先来考虑一个多项式：
$(x+a_1)(x+a_2)\dots (x+a_m)$
这个多项式的展开式中，根据韦达定理，或者说这里本身就是推导韦达定理的一种思路，我们可以知道常数项等于$a_1{a}_2\dots a_m$，$m$次项的系数是$1$，$m-1$次项系数是$\sum a_i$，$m-1$次项系数是$\sum _{i\ne j且i\le j}{a}_i{a}_j$，$\dots$

很容易看出，如果$a_1$、$a_2$、$\dots$、$a_m$都是素数，则$a_1{a}_2\dots a_m$的所有正因数之和即为$x=1$时的$(x+a_1)(x+a_2)\dots (x+a_m)$。

那么对于更复杂一点儿的情况，即素因式分解存在次幂高于一次的正整数，只要先考虑

$(x+a_1+b)(x+a_2)(x+a_3)\dots (x+a_m)$

代表了什么，再考虑

$(x+a_{(1,1)}+a_{(1,2)}+\cdots +a_{(1,{\alpha }_1)})(x+a_{(2,1)}+a_{(2,2)}+\cdots +a_{(2,{\alpha }_2)})(x+a_{(3,1)}+a_{(3,2)}+\cdots +a_{(3,{\alpha }_3)})\dots (x+a_{(m,1)}+a_{(m,2)}+\cdots +a_{(m,{\alpha }_m)})$

代表了什么，然后令$x=1$，就可以弄清楚

$(1+p_1+p_1^2+\cdots +p_1^{{\alpha }_1})(1+p_2+p_2^2+\cdots +p_2^{{\alpha }_2})\dots (1+p_m+p_m^2+\cdots +p_m^{{\alpha }_m})$

是怎么来的了

引申

对于任意一个有限的元素都是实数的集合 S = { a 1 , a 2 , … , a n } \;S=\{a_1,a_2,\dots,a_n\}\; S={a1​,a2​,…,an​}，我们定义它的所有元素的积为$P(S)$，另外令$P(\varnothing )=1$，根据上面一段的内容，很容易知道
$\sum _{A\subset S}P(A)=\prod _{i=1}^n(1+a_i)$

再进行延伸一下，如果我们令集合$S$中的元素可以重复，$a_i$重复了$m(i)$次，则有：
$\sum _{A\subset S}P(A)=\prod _{i=1}^n(1+\sum _{j=1}^{m(i)}{a}_{(i,j)})$

上面这两个式子就比较广泛了，举两个例子，可以当做小练习。
1.令 S = { 1 2 , 1 3 , … , 1 100 } \;S=\{\frac{1}{2},\frac{1}{3},\dots,\frac{1}{100}\}\; S={21​,31​,…,1001​}，求出来的结果十分奇妙。
2.在上面的第二个式子里令所有的$a_{(i,j)}=1$，则它的结果由求因数和变成了统计因数的个数。

总结

本总结与上文无关。学数学的时候经常会感到困难，不过这些也都是小问题，因为他们不会始终都是自己的困难，当自己第二次看的时候松动了，第三次第四次看，基本不再是困难了。因此啃数学书的时候不用因为看不懂而害怕，不用因为生涩而低估自己，多看几次最后看懂的时候或许赞叹一声不错，或许内心会感觉——就这？

这篇关于求一个正整数所有正因数的和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---