# 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.

--

--

## More from Pranav Ahluwalia

Computer Scientist Blog: www.pranav.ai Website: www.prandev.com

Love podcasts or audiobooks? Learn on the go with our new app.