LintCode_尾部的零

問題描述：

設計一個算法，計算出n階乘中尾部零的個數

樣例：11! = 39916800，是以應該傳回 2

算法實作：

方法一：這是個數學題，最開始就想到應該檢測n階乘中有多少個5的因子，是以采用一個for循環，周遊2~n的每個數，判斷能否被5整除，并且能拆分成多少個5的因子，這種方法非常耗時；

public static long trailingZeros(long n) {
      <span style="white-space:pre">	</span>//儲存n階乘中尾部零的個數
        long count=0;
        //儲存0~n中能整整除5的數的個數
        long count5=0;
      
        for(int i=5;i<=n;i=i+5){
              int j=i;
              while(j%5==0){
                count5++;
                j/=5;
             }
        }
      
        count=count5;
        return count;
    }
           

方法二：像5,10,15,20等數隻有一個5的因子，是以count5++就可以了，但碰到25,50,75等數，包含了2個5的因子，是以count5應該加2，碰到125等含3個5的因子，count5應該加3。是以，可以采用下面的算法。例如105的階乘，1~105有21個能被5整除的數，105/5=21，1~21中有4個能被5整除的數， 21/5=4，1~4中沒有，count5=21+4+0=25.即從1~105中挑出5=5*1,10=5*2，15=5*3,20=5*4,25=5*5,30=5*6...100=5*20,105=5*21這21個數，在從這21個數中挑出能繼續被5整除的25,50,75,100這四個數。

（當然，這種算法也是百度出來的）

public static long trailingZeros(long n) {
        long count=0;
        while(n>0){
            count+=(n/5);
            n/=5;
        }
        return count;
    }