Leetcode题目：Factorial Trailing Zeroes

题目：Given an integer n, return the number of trailing zeroes in n!.

Note: Your solution should be in logarithmic time complexity.

题目解答：

这个题目是要求出给定的整数n的阶乘结果后面有几个0。

可以发现，对于n!可以将它做质数分解：

n! = (2^a) * (3 ^ b) * (5 ^ c) * (7 ^ d) ……其中a,b,c,d >= 0。

 可以发现，阶乘结果末尾的0的产生，是由2和5的乘积个数决定的。

比如：

　　3! = 6 = 2 * 3 ，其中a = 1, c = 0 , 末尾0的个数是0。

　　4! = 24 = (2^3) * 3，其中a = 3,c = 0, 末尾0的个数是0。

　　5! = 120 = (2^3) * 3 * 5，其中a = 3，c = 1，末尾的0的个数是1。

　　6! = 720 = (2^4) * (3^2) * 5，其中，a = 4,c = 1，末尾的0 的个数是1。　　

以上例子足以说明，末尾的0的个数取决于2和5匹配产生的乘积的10的个数，取决于min(a,c)。

又可以看出，对于n!，a总是比c大，也就是说min(a,c)总是等于c的。也就是要统计n!中包含的5的因子的个数。

（1）首先统计包含一个5的： n / 5

（2）再统计包含两个5的：在上面的结果的基础上n再除以5

……

代码如下:

class Solution {
public:
    int trailingZeroes(int n) {
        int res = 0;
        while(n)
        {
            res += n / 5;
            n = n / 5;
        }
        return res;
    }
};