Question

Given an integer n, return the number of trailing zeroes in n!. 求n的阶乘n!末尾有多少个0

Algorithm

N!=K*10^M，且K不能被10整除，那么N!末尾有M个0。 对N!进行质因数分解，N!=(2^X)*(3^Y)^(5^Z)…，由于10=2*5，所以M只和X和Z有关，M=min(X,Z)。因为能被2整除的频率比能被5整除的数高很多，所以M=Z。 所以只要计算出Z的值，就可以得到N!末尾0的个数。

Z=[N/5] + [N/(5^2)] + [N/(5^3)] + … （总存在一个K，使得(5^K)>N，N/(5^K)=0）

Accepted Code：