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

问题： 给定一个整数N，那么N的阶乘就是N！末尾有多少个零？ （此题摘自《编程之美》）

解法1： 最喜欢的解法是如果N！ = K10M，且 K 不能被 10 整除，则 N！最后，M 为零。考虑N！质因数分解是可能的，N！ = (2X) * (3Y) * (5Z)...,那么从10开始.=第二个数字只与相关，当然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/ (52) + N/(53)+... 所以 N /5 意味着从 1 到 N 的数字中 5 的倍数它们贡献 5，N/(52) 意味着 52 倍数并贡献另外 5…。我举个简单的例子，如果你想知道从1到100分解数字时有多少个5，你可以知道有20个5的倍数和4个25的倍数，所以总共是24个5。代码如下：

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

总结： 上面的分析平淡无奇，但是有一点值得一提的是算术基本定理，即 每个大于 1 的自然数都可以因式分解为素数，而且这种分解方法是独一无二的。 定理的证明分为两部分，存在性和唯一性。证明如下：

存在性证明

用反证法证明存在大于1的自然数不能写成素数的乘积，并称最小的n。自然数根据其可整性（是否可以表示为两个非自身的自然数的乘积）可以分为三类：素数、合数和 1。

• 首先，根据定义 n 大于
• 其次，n 不是素数，因为素数 p 可以写成素数的乘积：p=p，这与假设相矛盾。因此，n 只能是合数，但每个合数都可以分解为两个严格小于自身且大于 1 的自然数的乘积。假设 n = a*b，a 和b 都是大于 1 且小于 n 的数。从假设可以看出，a和b都可以因式分解为素数的乘积，因此n也可以因式分解为素数的乘积，所以这与假设相矛盾。这证明了所有大于1的自然数都可以分解为素数的乘积。

唯一性证明

• 当n=1时，确实只有一次分解。
• 假设对于自然数 n>1，有两种分解可供分解：n=p1...pm = q♝ , p1