算法面试题：阶乘末尾含0问题

题： 给定一个整数N，那么N的阶乘N！末尾有多少个0呢？（该题取自《编程之美》）

解1： 流行的解法是，如果 N！= K10^M，且K不能被10整除，则 N！末尾有 M 个0。考虑 N！可以进行质因数分解，N！= (2^X) * (3^Y) * (5^Z)..., 则由于10 = 25，所以0的个数只与 X 和 Z 相关，每一对2和5相乘得到一个 10，所以 0 的个数 M = min(X， Z)，显然 2 出现的数目比 5 要多，所以 0 的个数就是 5 出现的个数。由此可以写出如下代码：

/**
 * N!末尾0的个数
 */
int numOfZero(int n)
{
    int cnt = 0, i, j;
    for (i = 1; i <= n; i++) {
        j = i;
        while (j % 5 == 0) {
            cnt++;
            j /= 5;
        }
    }
    return cnt;
}
复制代码

解2： 继续分析可以改进上面的代码，为求出1到N的因式分解中有多少个5，令 Z=N/5 + N/(5²) + N/(5³)+... 即 N/5 表示 1 到 N 的数中 5 的倍数贡献一个 5，N/(5²) 表示 5² 的倍数再贡献一个 5...。举个简单的例子，比如求1到100的数因式分解中有多少个5，可以知道5的倍数有20个，25的倍数有4个，所以一共有24个5。代码如下：

/**
 * N!末尾0的个数-优化版
 */
int numOfZero2(int n)
{
    int cnt = 0;
    while (n) {
        cnt += n/5;
        n /= 5;
    }
    return cnt;
}
复制代码

总结： 上面的分析乏善可陈，不过需要提到的一点就是其中涉及到的一条算术基本定理，也就是 任意大于1的自然数都可以分解为质数的乘积，而且该分解方式是唯一的。 定理证明分为两个部分，存在性和唯一性。证明如下：

存在性证明

使用反证法来证明，假设存在大于1的自然数不能写成质数的乘积，把最小的那个称为n。自然数可以根据其可除性（是否能表示成两个不是自身的自然数的乘积）分成3类：质数、合数和1。

• 首先，按照定义，n大于1。
• 其次，n 不是质数，因为质数p可以写成质数乘积：p=p，这与假设不相符合。因此n只能是合数，但每个合数都可以分解成两个严格小于自身而大于1的自然数的积。设 n = a*b，a 和 b都是大于1小于n的数，由假设可知，a和b都可以分解为质数的乘积，因此n也可以分解为质数的乘积，所以这与假设矛盾。由此证明所有大于1的自然数都能分解为质数的乘积。

唯一性证明

• 当n=1的时候，确实只有一种分解。
• 假设对于自然数n>1，存在两种因式分解: n=p₁...p_m = q₁...q_k，p₁<=...<=p_m， q₁<=...<=q_k。其中p和q都是质数。我们要证明 p₁=q₁...如果不相等，我们可以设 p₁ < q₁，从而 p₁ 小于所有的 q，由于 p₁ 和 q₁ 是质数，所以它们的最大公约数为1，由欧几里德算法可知存在整数 a 和 b 使得 a * p₁ + b * q₁ = 1。因此 a * p₁ * q₂...q_k + b * q₁ * q₂...q_k = q₂...q_k。由于 q₁...q_k = n，因此 p₁ 除尽右边的 q₂...q_k，即 q₁...q_k / q₁ 为整数，且 q₂...q_k 有一个质数因子分解，在此因式分解中 p₁ 出现，但是 q₂...q_k < n，所以它有一个唯一的因式分解（由归纳法），此矛盾表明，p₁ 最终一定等于 q₁，所以 p₁ 能够除尽两个 n 的因子分解p₁...p_m 和 q₁...q_k，从而 p₂...p_m = q₂...q_k < n，另一个因子也相等（由归纳法）。由此完成唯一性的证明。