约数个数定理（求解因数的个数）

整数的唯一分解定理

对于一个大于1正整数n可以分解质因数：

约数个数定理

则n的正约数的个数就是

。

其中a1、a2、a3…ak是p1、p2、p3，…pk的指数。

定理简证

编辑

首先同上，n可以分解质因数：n=p1^a1×p2^a2×p3^a3*…*pk^ak,

由约数定义可知p1^a1的约数有:p1^0, p1^1, p1^2......p1^a1 ，共（a1+1）个;同理p2^a2的约数有（a2+1）个......pk^ak的约数有（ak+1）个。

故根据乘法原理：n的约数的个数就是(a1+1)(a2+1)(a3+1)…(ak+1)。

乘法原理

做一件事，完成它需要分成n个步骤，做第一 步有m1种不同的方法，做第二步有m2种不同的方法，……，做第n步有mn种不同的方法。那么完成这件事共有 N=m1×m2×m3×…×mn 种不同的方法。

例题链接:UVA-294https://vjudge.net/problem/UVA-294

约数和公式

对于已经分解的整数A=(p1^k1)*(p2^k2)*(p3^k3)*....*(pn^kn)

有A的所有因子之和为

    S = (1+p1+p1^2+p1^3+...p1^k1) * (1+p2+p2^2+p2^3+….p2^k2) * (1+p3+ p3^3+…+ p3^k3) * .... * (1+pn+pn^2+pn^3+...pn^kn)