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：