作业帮正整数N的所有正因数和公式推导
来源：学生作业帮助网 编辑：作业帮 时间：2024/05/05 04:48:42
正整数N的所有正因数和公式推导
正整数N的所有正因数和公式推导
正整数N的所有正因数和公式推导
给定一个正整数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整除的,等等,然后利用容斥原理的公式求得.
我的这个比较好理如果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的所有正因数和即为
全部展开
我的这个比较好理如果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)
收起
回答 共 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。 ...
全部展开
回答 共 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
收起