首页 > 代码库 > 求N！末尾所得数字0的个数
求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 <=0) return 0; int ret = 0,i,j; for(i = 1;i < value;i++){ j = i; while(j % 5 == 0){ ret++; j /= 5; } } return ret ; }
求N！末尾所得数字0的个数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。