# 算一算N阶乘的尾随零个数

3!(阶乘符号,下同) = 3 * 2 * 1 = 6, 尾随零个数为0

5! = 5 * 4 * 3 * 2 * 1 = 120, 尾随零个数为1

10! = 10 * 9 * … * 1 = 3628800, 尾随零个数为2

OK,明白问题之后,我们就来尝试算一算吧~

##### 方法1

```function factorial(n)
local val = 1
for i = 2, n do
val = val * i
end
return val
end

function trailing_zero_count(value)
local count = 0
while value % 10 == 0 do
count = count + 1
value = value / 10
end
return count
end

function factorial_trailing_zero_count(n)
local value = factorial(n)
return trailing_zero_count(value)
end```
##### 方法2

10 = 2 * 5

N! = N * (N - 1) * (N - 2) * … * 1

factor_2_count(A)

factor_5_count(B)

factor_2_count(N!) = factor_2_count(N) + factor_2_count(N - 1) + factor_2_count(N - 2) + … + factor_2_count(1)

factor_5_count(N!) = factor_5_count(N) + factor_5_count(N - 1) + factor_5_count(N - 2) + … + factor_5_count(1)

10 = 2 * 5 (一个2因子和一个5因子构成一个10因子)

min(factor_2_count(N!), factor_5_count(N!)) (min为最小值函数)

```function factor_2_count(n)
local count = 0
while n % 2 == 0 do
count = count + 1
n = n / 2
end
return count
end

function factorial_factor_2_count(n)
local count = 0
for i = 1, n do
count = count + factor_2_count(i)
end
return count
end

function factor_5_count(n)
local count = 0
while n % 5 == 0 do
count = count + 1
n = n / 5
end
return count
end

function factorial_factor_5_count(n)
local count = 0
for i = 1, n do
count = count + factor_5_count(i)
end
return count
end

function factorial_trailing_zero_count_v2(n)
return math.min(factorial_factor_2_count(n), factorial_factor_5_count(n))
end```
##### 方法3

factor_2_count(N!) >= factor_5_count(N!)

min(factor_2_count(N!), factor_5_count(N!)) = factor_5_count(N!)

```function factor_5_count(n)
local count = 0
while n % 5 == 0 do
count = count + 1
n = n / 5
end
return count
end

function factorial_factor_5_count(n)
local count = 0
for i = 1, n do
count = count + factor_5_count(i)
end
return count
end

function factorial_trailing_zero_count_v3(n)
return factorial_factor_5_count(n)
end```
##### 方法4

n1 = N / 5

n2 = N / (5 * 5) = N / 25

n3 = N / (5 * 5 * 5) = N / 125

n4 = N / (5 * 5 * 5 * 5) = N / 625

n1 + n2 + n3 + n4 + …

```function factorial_trailing_zero_count_v4(n)
local count = 0
local factor = 5
while n >= factor do
count = count + math.floor(n / factor)
factor = factor * 5
end
return count
end```

OK,我们下次再见吧~

113 篇文章22 人订阅

0 条评论

4727

3960

2562

5035

3217

2497

3138

3209

1734

712