n! | adamponting.com

Legendre’s formula:

The exponent of $p$ in the prime factorization of $n!$ is

$e_p(n!)= \sum_{r\ges 1} {\Big\lfloor \frac{n}{p^r} \Big\rfloor}$

This is equivalent to:

$n! = \prod_{p\les n} p^{\lfloor n/p \rfloor +\lfloor n / p^2 \rfloor +\lfloor n / p^3 \rfloor +\dots }$

Explanation: Between $1$ and $n$ there are $\lfloor n/p \rfloor$ numbers that are multiples of $p$ : $p,2p,3p,\dots,\lfloor n/p \rfloor p$ . (e.g. if $p=3$ and $n=10$ , these are $3, 6, 9$ .) These each contribute a factor of $p$ . Of those, there are $\lfloor n/p^2 \rfloor$ multiples of $p^2$ that each contribute one more factor of $p$ . (e.g. one more: $3^2=9$ . 4 factors in total.) The multiples of $p^3$ contribute one more factor, etc until $\lfloor n/p^r \rfloor=0$ .
Example: Find the exponent of $5$ in the prime factorization of $1000!$ .

$\Big\lfloor \frac{1000}{5} \Big\rfloor + \Big\lfloor \frac{1000}{5^2} \Big\rfloor + \Big\lfloor \frac{1000}{5^3} \Big\rfloor + \Big\lfloor \frac{1000}{5^4} \Big\rfloor = 200 + 40 + 8 + 1 = 249.$