数论 求因数个数

因数是什么?

假如 a * b = c （a、b、c都是整数)，a和b就是c的因数。

两个正整数相乘，那么这两个数都叫做积的因数。

例如：

6的因数是1，2，3，6

因数个数算法：

即任何一个大于1 的整数 n 都可以分解：

n = pow(p1,a1) * pow(p2,a2) * pow(p3,a3) ....... * pow(pk,ak)

(其中p 代表着质数)

n 的 因数个数：

（a1+1） * (a2 +1) * (a3 +1) * .....* (ak +1 0

证明：

p1a1 = pow(p1,a1) 的因数数个数有 a1+1 个 ( p0,p1,p2,p3,p4 ...... , pa1)

那么 p2a2的因数个数有 a2+2个。

那么他们相乘的因数个数就有 (a1+1) * (a2+1)

例如

15 = 31 * 51 = pow(3,1)*pow(5,1)

31 的因数个数有 2 个，31，30

51 的因数个数有 2 个，51，50

那么15的因数个数就有4 个。(1,3,5,15)

31*51= 15

31*50= 3

30*51= 5

30*50= 1