正因数的和怎么求

问题描述

精选答案

给定一个正整数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整除的，等等，然后利用容斥原理的公式求得。