In mathematics, Legendre's formula gives an expression for the exponent of the largest power of a prime p that divides the factorial n!. It is named after Adrien-Marie Legendre. It is also sometimes known as de Polignac's formula, after Alphonse de Polignac.

For any prime number p and any positive integer n, let ${\displaystyle \nu _{p}(n)}$ be the exponent of the largest power of p that divides n (that is, the p-adic valuation of n). Then

where ${\displaystyle \lfloor x\rfloor }$ is the floor function. While the sum on the right side is an infinite sum, for any particular values of n and p it has only finitely many nonzero terms: for every i large enough that ${\displaystyle p^{i}>n}$, one has ${\displaystyle \textstyle \left\lfloor {\frac {n}{p^{i}}}\right\rfloor =0}$. This reduces the infinite sum above to

where ${\displaystyle L=\lfloor \log _{p}n\rfloor }$.

For n = 6, one has ${\displaystyle 6!=720=2^{4}\cdot 3^{2}\cdot 5^{1}}$. The exponents ${\displaystyle \nu _{2}(6!)=4,\nu _{3}(6!)=2}$ and ${\displaystyle \nu _{5}(6!)=1}$ can be computed by Legendre's formula as follows:

Since ${\displaystyle n!}$ is the product of the integers 1 through n, we obtain at least one factor of p in ${\displaystyle n!}$ for each multiple of p in ${\displaystyle \{1,2,\dots ,n\}}$, of which there are ${\displaystyle \textstyle \left\lfloor {\frac {n}{p}}\right\rfloor }$. Each multiple of ${\displaystyle p^{2}}$ contributes an additional factor of p, each multiple of ${\displaystyle p^{3}}$ contributes yet another factor of p, etc. Adding up the number of these factors gives the infinite sum for ${\displaystyle \nu _{p}(n!)}$.

One may also reformulate Legendre's formula in terms of the base-p expansion of n. Let ${\displaystyle s_{p}(n)}$ denote the sum of the digits in the base-p expansion of n; then

For example, writing n = 6 in binary as 6₁₀ = 110₂, we have that ${\displaystyle s_{2}(6)=1+1+0=2}$ and so