有效判断1024！末尾0的方法

【出自GG面试题】

难度系数：★★★★ 被考察系数：★★★★☆

分析与解答：

方法一：蛮力法

最简单的方法就是计算出1024！的值，然后判断末尾有多少个0，但是这种方法有两个非常大的缺点：第一，算法的效率非常低；第二，当这个数字比较大的时候直接计算阶乘可能会导致数据溢出，从而导致计算结果出现偏差。因此，下面给出一种比较巧妙的方法。

方法二：因子法

5与任何一个偶数相乘都会增加末尾0的个数，由于偶数的个数肯定比5的个数多，因此，1～1024所有数字中有5的因子的数字的个数决定了1024！末尾0的个数。因此，只需要统计因子5的个数即可。此外5与偶数相乘会使末尾增加一个0，25（有两个因子5）与偶数相乘会使末尾增加两个0，125（有三个因子5）与偶数相乘会使末尾增加3个0，625（有四个因子5）与偶数相乘会使末尾增加四个0。对于本题而言：

是5的倍数的数有：a1=1024/5=204个

是25的倍数的数有：a2=1024/25=40个（a1计算了25中的一个因子5）

是125的倍数的数有：a3=1024/125=8个（a1，a2分别计算了125中的一个因子5）(www.xing528.com)

是625的倍数的数有：a4=1024/625=1个（a1，a2，a3分别计算了625中的一个因子5）

所以，1024！中总共有a1+a2+a3+a4=204+40+8+1=253个因子5。因此，末尾总共有253个0。根据以上思路实现代码如下：

程序的运行结果如下：

1024！末尾0的个数为：253

算法性能分析：

由于这种方法循环的次数为n/5，因此，算法时间复杂度为O（N）。

引申：如何计算N！末尾有几个0

分析与解答：

从以上的分析可以得出N！末尾0的个数为N/5+N/5^2+N/5^3+N/5^m（5^m＜N且5^（m+1）＞N）。