Contando múltiplos de p, p², p³, ...
La Fórmula de Legendre (que también se conoce como la Fórmula de de Polignac) es un resultado fundamental en la teoría de números que sirve para encontrar la mayor potencia de un primo $p$ que divide a $n!$ ($n$ factorial). En las olimpiadas de mate, vas a ver que este exponente se escribe como $v_p(n!)$, la valuación $p$-ádica de $n!$. Esta herramienta es clave para problemas que tienen que ver con divisibilidad de factoriales, coeficientes binomiales y productos de enteros consecutivos. La puedes usar muy seguido para ver cuántos ceros hay al final de un factorial o para analizar la factorización en primos de expresiones como $\binom{n}{k}$.
La idea detrás de la fórmula viene de un argumento de conteo sistemático. Para encontrar el total de factores de $p$ en el producto $n! = 1 \times 2 \times \dots \times n$, podrías intentar contar primero cuántos números en la lista son múltiplos de $p$. Pero ojo, solo contar los múltiplos de $p$ no es suficiente, porque los múltiplos de $p^2$ te dan dos factores de $p$, los múltiplos de $p^3$ te dan tres, y así te vas.
Para solucionar esto, la Fórmula de Legendre usa una estrategia de "capas". En lugar de preguntar "¿cuántos factores de $p$ aporta el número $m$?", la idea es preguntar "¿cuántos números aportan un $k$-