求N!末尾0的个数

题目

给定一个整数N，那么N的阶乘 N! 末尾有多少个0呢？ (N≤1000000000)

方法一

最容易想到的方法，先把N的阶乘求出来，再用一个函数计算末尾0的个数，但是这个方法有两个问题：当数字很大时，效率很差、用内置类型（int、long等）会溢出。要解决这两个问题，只能优化算法。

首先要知道N的阶乘一定可以用K×10^M来表示，那我们的问题就变成了求M。又因为10 只能分解成 2 * 5，所以只需要求出 2 的个数和 5 的个数中的最小值，就得到了M。 而任何数因数分解后，2 的个数 一定多于 5 的个数（因为2的倍数比5的倍数多），所以 这个题最后又变成 了求 5 的个数。

可知 5 的倍数一定是隔 5 个数字出现一次，那么就可以修改一下循环条件不需要从1开始。

int NumOf0(int n){
    int num = 0;
    for (int i = 5; i <= n; i += 5){
        int j = i;
        /*每除得一个5，就说明末尾有一个0*/
        while (j % 5 == 0){
            num++;
            j /= 5;
        }
    }
    return num;
}

方法二

上面得到了结论：求出 5 的个数就是末尾0的个数。随着数字的增加，能提取出来的 5 的个数越来越多，循环次数会增加，为了减少循环次数，我们可以提取5 , 5^2 , 5^3 …可以提高效率5 的个数 Y 可得到公式：Y = [N/5] + [N/5^2] + [N/5^3] + …

int NumOf0_fast(int n){
    int num = 0;

    while (n != 0){
        num += n / 5;
        n /= 5;
    }

    return num;
}