Legendre's formula

Statement

Let $p$ be a prime number and let $n$ be a natural number. Let $\nu_p$ be the p-adic valuation. Then $$\nu_p(n!) = \sum_{i=1}^{\infty} \left\lfloor \frac{n}{p^i} \right\rfloor.$$ The sum is finite, because $\lfloor n / p^i \rfloor = 0$ when $p^i > n$.

Remarks

An equivalent form: $\nu_p(n!) = \dfrac{n - s_p(n)}{p - 1}$, where $s_p(n)$ is the sum of the digits of $n$ in base $p$. For example, $\nu_2(10!) = 5 + 2 + 1 = 8$, and $\nu_5(100!) = 20 + 4 = 24$. So $100!$ ends with $24$ zeros. The proof counts, for each $i$, the multiples of $p^i$ among $1, \dots, n$.

Explanations

L1 human

To count the factors $p$ in $n!$, count the multiples of $p$ up to $n$. Then add the multiples of $p^2$, which give a second factor, and so on. For $10!$ and $p = 3$: there are $3$ multiples of $3$ and $1$ multiple of $9$, so $3^4$ is the largest power of $3$ that divides $10!$.