LintCode 尾部的零题目分析代码

题目

设计一个算法，计算出n阶乘中尾部零的个数

分析

例子：（1000的阶乘末尾0的个数）**** 1000 / 5 + 1000 / 25 + 1000 / 125 + 1000 / 625 = 200 + 40 + 8 + 1 = 249(个**)

原理是： 假如你把1 × 2 ×****３****× 4 ×……×N****中每一个因数分解质因数，结果就像：**** 1 × 2 × 3 × (2 × 2) × 5 × (2 × 3) × 7 × (2 × 2 ×2) ×…… 10****进制数结尾的每一个****0****都表示有一个因数****10****存在****——****任何进制都一样，对于一个****M****进制的数，让结尾多一个****0****就等价于乘以****M****。**** 10****可以分解为****2 × 5——****因此只有质数****2****和****5****相乘能产生****0****，别的任何两个质数相乘都不能产生****0****，而且****2****，****5****相乘只产生一个****0****。**** ****所以，分解后的整个因数式中有多少对****(2, 5)****，结果中就有多少个****0****，而分解的结果中，****2****的个数显然是多于****5****的，因此，有多少个****5****，就有多少个****(2, 5)****对。**** ****所以，讨论****1000****的阶乘结尾有几个****0****的问题，就被转换成了****1****到****1000****所有这些数的质因数分解式有多少个****5****的问题。**** 5****的个数可以用上面那个式子算出（道理很简单，自己想想吧****_****），所以****1000****的阶乘结尾有****249****个****0****。****

10000以内**** 0****的个数就是****=5****的倍数****+52****的倍数****+53****的倍数****+54****的倍数****+55****的倍数** **

代码

class Solution {
    /*
     * param n: As desciption
     * return: An integer, denote the number of trailing zeros in n!
     */
    public long trailingZeros(long n) {
        // write your code here
        long sum = 0;
        while (n != 0) {
            sum += n / 5;
            n /= 5;
        }
        return sum;
    }
};