Formula

Exponent of a prime in $n!$ (Legendre's formula)

Arithmetic • Number System • Factors and Divisors

Formula

⌊ \frac{n}{p} ⌋ + ⌊ \frac{n}{p ^{2}} ⌋ + ⌊ \frac{n}{p ^{3}} ⌋ + \dots

For a prime

p

and a positive integer

n

, the exponent of

p

in the prime factorisation of

n!

⌊ \frac{n}{p} ⌋ + ⌊ \frac{n}{p ^{2}} ⌋ + ⌊ \frac{n}{p ^{3}} ⌋ + \dots

, the sum stopping as soon as

p^{k} > n

How to use it

1The number of trailing zeros of $n!$ is the exponent of $5$ alone, because the $5$ s always run out before the $2$ s.
2For the largest power of a composite $m$ dividing $n!$ , apply the formula to each prime of $m$ and take the smallest of the results after dividing by that prime's multiplicity in $m$ .
3Each term counts one extra factor for the multiples of the next power, which is why $25$ contributes two $5$ s and $125$ three.

Worked example

In how many zeros does

30!

end?

Step-by-step

1
zeros $=$ exponent of $5$ in $30!$
Why: A trailing zero needs a $2$ and a $5$ , and $30!$ holds far more $2$ s than $5$ s.
2
$⌊ \frac{30}{5} ⌋ + ⌊ \frac{30}{25} ⌋ = 6 + 1 = 7$
Why: $125 > 30$ , so the sum stops after two terms.

Answer

7

Watch out

Counting only the multiples of

p

misses the extra factors hidden inside

p^{2}

p^{3}

\dots

— the commonest error. And the exponent of

10

is the SMALLER of the exponents of

2

and

5

, never their sum.

Builds on

Prime factorisation

Also known as

Legendre's formula, trailing zeros of a factorial, highest power of a prime dividing n factorial, number of zeros at the end of n!, de Polignac's formula, largest power of 10 dividing a factorial

Appears in past papers

2018 (I)

Q83