# Trailing Zeros of A Factorial With Legendre’s Formula

# Legendre’s Formula

There is a theorem in number theory known as *Legendre’s Formula*. It states that if N is a positive integer and p is a prime number, then the highest power of p that divides N! is given by the following formula

Translating math to english this reads “The highest power of p that divides N! is the infinite sum of the floor of N divided by p to the current exponent”

We know that the infinite sum will eventually reach a terminal value of 0 as at some point, we will reach a large enough exponent for p that the result of dividing n by p raised to i is less than 1. And taking the floor of any value less than 1 will give us 0. Therefore, we do not need to worry about adding up an infinite amount of quotients unless our N is astronomically large.

# Adaptation For Trailing Zeros

This formula will allow us to determine the highest power of p in N!. But what about non-prime values? We can take the prime factorization of our target number and run separate instances of the function. Since 10 is the product of 2 and 5, we can simply take the minimum value returned by running the formula on 2, and then 5.

But, knowing that powers of 5 will always be larger than powers of two, the number returned by Legendre’s formula for 5 will always be smaller. Therefore, we can dispense with the minimum function altogether and simply find out how many exponents of 5 divide into the factorial. This will give us the number of trailing zeros.

# Example Problems

## Trailing zeros in 100!

We have 24 trailing zeros in 100!

## Trailing zeros in 95!

We have 22 traling zeros in 95!

# Trailing Zeros Coding Question

Suppose we want to write a program to find the number of trailing zeros in n!. We can simply translate our algorithm into code. We will use a while loop to iterate until the floor of our number divided by 5 to our current exponent yields zero. While iterating we will track the sum and return it upon termination. Leetcode features this exact question.

**def** **trailingZeroes**(self, n: int) **->** int:

power **=** 1

sum **=** 0

**while** (n**//**(5******power) **!=** 0):

sum**+=**(n**//**(5******power))

power**+=**1

**return** sum

*Originally published at **https://www.pranav.ai** on June 8, 2021.*