正整数N的所有正因数和公式推导

发布网友 发布时间：2022-05-05 23:44

我来回答

共3个回答

热心网友 时间：2022-06-29 13:40

回答 共 2 条
给定一个正整数N，求出它的所有正因数没有什么公式，只有正因数的个数是有公式的。这个公式就是
如果N的素因数分解为N=p1^(m1)p2^(m2)...pk^(mk)，
那么正整数N所有正因数的个数就是
N*(1-1/p1)*(1-1/p2)...*(1-1/pk)。
举个例子：如果N=900，那么N=2^2*3^2*5^2。
按照公式900的所有正因数的个数是900*(1-1/2）*(1-1/3）*(1-1/5）=240。
这个公式的证明就是用容斥原理，就是考虑N的正因数中能被p1整除的、能被p2整除的，等等，然后利用容斥原理的公式求得。
回答者： china_wc - 魔法师 五级 5-23 23:36
我的这个比较好理解：如果N可分解为a^m*b^n*c^p…… 那末N的所有正因数和为
(1+a+a^2+……+a^m)*(1+b+b^2+……+b^n)*(1+c+c^2+……+c^p)……
简略证明如下：由乘法法则可知，上述括号的连乘积为从所有括号中各取一个相乘，这样就可以保证它包含所有因数
稍微举个简单的例子更好理解：216=2^3*3^3 那末216的所有正因数和即为
(1+2+4+8)*(1+3+9+27)
回答者： XshEdmond - 试用期 一级 5-24 00:09

热心网友 时间：2022-06-29 13:41

我的这个比较好理解：如果N可分解为a^m*b^n*c^p…… 那末N的所有正因数和为
(1+a+a^2+……+a^m)*(1+b+b^2+……+b^n)*(1+c+c^2+……+c^p)……
简略证明如下：由乘法法则可知，上述括号的连乘积为从所有括号中各取一个相乘，这样就可以保证它包含所有因数
稍微举个简单的例子更好理解：216=2^3*3^3 那末216的所有正因数和即为
(1+2+4+8)*(1+3+9+27)

热心网友 时间：2022-06-29 13:41

给定一个正整数N，求出它的所有正因数没有什么公式，只有正因数的个数是有公式的。这个公式就是
如果N的素因数分解为N=p1^(m1)p2^(m2)...pk^(mk)，
那么正整数N所有正因数的个数就是
N*(1-1/p1)*(1-1/p2)...*(1-1/pk)。
举个例子：如果N=900，那么N=2^2*3^2*5^2。
按照公式900的所有正因数的个数是900*(1-1/2）*(1-1/3）*(1-1/5）=240。
这个公式的证明就是用容斥原理，就是考虑N的正因数中能被p1整除的、能被p2整除的，等等，然后利用容斥原理的公式求得。