一个阶乘中末尾零的个数

   //给定一个正整数n，请计算n的阶乘n！末尾所含有“0”的个数。

• 5！=120，其末尾所含有的“0”的个数为1；
• 10！= 3628800，其末尾所含有的“0”的个数为2；
• 20！= 2432902008176640000，其末尾所含有的“0”的个数为4。
• //分析：
• 两个数相乘尾数0的个数其实就是依赖于2和5因子的个数
• 每两个连续数字就会有一个因子2
• 只需要关心5因子的个数
• n = 5*K + r（0<= r <= 4）
• n! = (5*K) * (5*(K-1)) * (5*(K-2)) * ... * 5 * A
• f(n!) = g(n!) = g(5^K * K! * A) = K + g(K!) = K + f(K!)，其中K=n / 5（取整数）。
• 0 <= n <= 4时，f(n!)=0
• • f(5!) = 1 + f(1!) = 1
  • f(10!) = 2 + f(2!) = 2
  • f(20!) = 4 + f(4!) = 4
  • f(100!) = 20 + f(20!) = 20 + 4 + f(4!) = 24
  • f(1000!) = 200 + f(200!) = 200 + 40 + f(40!) = 240 + 8 + f(8!) = 248 + 1 + f(1) =249

 1 #include <iostream>
 2 using namespace std;
 3 
 4 int GetN_1(int n)
 5 {
 6 if (n < 5)
 7 {
 8 return 0;
 9 }
10 else
11 {
12 return (n / 5 + GetN_1(n / 5));//利用递归找一个阶乘中末尾零的个数
13 }
14 }
15 int GetN_2(int n)//采用循环的方式找一个阶乘中末尾零的个数
16 {
17 int m, count=0;
18 for(int i=1;i<=n;i++)
19 {
20 m=i;
21 while(m%5==0)
22 {
23 count++;
24 m/=5;
25 }
26 
27 }
28 return count;
29 }
30 int main()
31 {
32 cout << GetN_1(1000) << endl;
33 cout << GetN_2(1000) << endl;
34 
35 return 0;
36 }