This site is supported by donations to The OEIS Foundation.

# De Polignac–Legendre formula

The prime factorization of
 n!, n   ≥   1,
is given by de Polignac's formula, named after Alphonse de Polignac. L. E. Dickson attributes the formula to Legendre.[1]

## Formula

The prime factorization of
 n!
,
 n   ≥   1
, is given by
${\displaystyle {\begin{array}{l}\displaystyle {n!=\prod _{\stackrel {\scriptstyle p{\text{ prime}}}{p\leq n}}p^{\operatorname {ord} _{p}\,n!},}\end{array}}}$

where

${\displaystyle {\begin{array}{l}\displaystyle {\operatorname {ord} _{p}\ n!=\sum _{k=1}^{\lfloor \log _{p}(n)\rfloor }\left\lfloor {\frac {n}{p^{k}}}\right\rfloor ,}\end{array}}}$
 n!
(order of prime
 p
in the prime factorization of
 n!
) and the brackets represent the floor function.

## Examples

Consider

${\displaystyle {\begin{array}{l}\displaystyle {5!=1\cdot 2\cdot 3\cdot 4\cdot 5=2^{3}\cdot 3^{1}\cdot 5^{1},}\end{array}}}$
for which the
 p
${\displaystyle {\begin{array}{l}\displaystyle {\operatorname {ord} _{2}\ 5!=\sum _{k=1}^{\lfloor \log _{2}(5)\rfloor }\left\lfloor {\frac {5}{2^{k}}}\right\rfloor =\left\lfloor {\frac {5}{2^{1}}}\right\rfloor +\left\lfloor {\frac {5}{2^{2}}}\right\rfloor =2+1=3,}\end{array}}}$
${\displaystyle {\begin{array}{l}\displaystyle {\operatorname {ord} _{3}\ 5!=\sum _{k=1}^{\lfloor \log _{3}(5)\rfloor }\left\lfloor {\frac {5}{3^{k}}}\right\rfloor =\left\lfloor {\frac {5}{3^{1}}}\right\rfloor =1,}\end{array}}}$
${\displaystyle {\begin{array}{l}\displaystyle {\operatorname {ord} _{5}\ 5!=\sum _{k=1}^{\lfloor \log _{5}(5)\rfloor }\left\lfloor {\frac {5}{5^{k}}}\right\rfloor =\left\lfloor {\frac {5}{5^{1}}}\right\rfloor =1.}\end{array}}}$