[转]阶乘 n! 末尾 0 的个数

 

分析：

n! 末尾有多少个 0 取决于从 1 到 n 的各个数的因子中 2 和 5 的个数。又因为 2 的个数远远多于 5 的个数，所以只要求出这当中 5 的个数即可。不断地用 n 除以 5，直到结果为 0，将中间的结果都加起来，即可得到因子 5 的个数。例如，100/5 = 20，20/5 = 4，4/5 = 0。因此，1 到 100 中因子 5 的个数为 (20 + 4) = 24 个，亦即 100! 末尾有 24 个 0。

代码如下：

#include <cstddef>

std::size_t ntrailingzero(std::size_t n)
{
    std::size_t cnt = 0;
    while ( n /= 5 )
    {
        cnt += n;
    }
   
    return cnt;
}

这个计算方法正确性的证明网上有很多，搜索一下就知道了。不过，目前我还没找到计算 n! 中一共有多少个 0 的简便算法，知道的人请举手。谢谢~