求N！末尾所得数字0的个数

题目：给定一个整数N ，那么N 的阶乘N ！末尾有多少个0呢？

例如：N = 10，N! = 3628800,所以N！末尾就有2个零。

分析：如果直接先算出N!阶乘，很容易导致内存溢出。显然，直接算出来是不行的。所以，我们可以换一个角度来分析这个问题。我们知道

　　N! = 1*2*3*4*......*N，所以，我们可以对N！进行分解质因数。即N! = 2^x * 3^y * 5 ^z........可以看到2和5相乘，必然会产生一个零。那么问题就转化为2^x * 5^z可以产生多少个零就可以了。即求出min(x,z)。显然x大于z(能被2整除的肯定比能被5整除的多)，故我们只需要求出1...N能够分解出多少个5就行了。

代码：

# python 版

def count_zero_number(value):

        if not isinstance(value,int):

                raise TypeError("参数必须为整型")

        res = 0

        if value <= 0:

            return 0

        i = 1

        while i <= value:

                j = i  # 保存当前i的值

                while j % 5 == 0:  # 判断当前值是否含有重复质数

                        count += 1

                        j = j // 5 # 更新j的值

                i += 1

        return count

# Cpp版

int count_zero_number(int value){

        if(value <=)

              return ;

        int ret = ,i,j;

        for(i = ;i < value;i++){

                j = i;

                while(j %  == ){

                        ret++;

                        j /= ;

        }

    }

    return ret ;

}

巴特西

求N！末尾所得数字0的个数

最新文章

热门文章