(Legendre's Formula)

We recall the factorial notation: for an integer $n, n! = n \times (n-1) \times \ldots \times 2 \times 1$.

For a prime number $p$, calculate $v_{p}(n!)$.
This is the Legendre formula: $v_{p}(n!)=\Sigma_{k=1}^{+\infty}\left\lfloor\frac{n}{p^{k}}\right\rfloor$. First, note that this sum is not infinite because when $k$ becomes sufficiently large, $p^{k}$ exceeds $n$ and thus $\left\lfloor\frac{n}{p^{k}}\right\rfloor=$ 0.

To calculate $v_{p}(n!)$, it suffices to add the p-adic valuations of all integers less than or equal to $n$. Most of these integers are not divisible by $p$ and thus their p-adic valuation is zero. There are exactly $\left\lfloor\frac{n}{p}\right\rfloor$ that are divisible by $p$. Among them, those divisible by $p^{2}$ must be counted multiple times, and there are $\left\lfloor\frac{n}{p^{2}}\right\rfloor$ of them. At this point, with $\left\lfloor\frac{n}{p}\right\rfloor+\left\lfloor\frac{n}{p^{2}}\right\rfloor$, only the p-adic valuations greater than or equal to $3 n^{\prime}$ have not been fully counted (they have only added 2 to the sum). Therefore, it is necessary to continue adding $\left\lfloor\frac{n}{p^{3}}\right\rfloor$, etc.