数论 求因数个数

因数是什么?

  假如 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)

    3的因数个数有  2 个,31,30

    5的因数个数有  2 个,51,50

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

    31*51=  15

    31*50=  3

    30*51=  5

    30*50=  1

原文地址:https://www.cnblogs.com/--zz/p/10513309.html