Potencia de un divisor en el factorial

Se dan dos números $n$ y $k$. Hallar el mayor entero $x$ tal que $k^x$ divide a $n!$.

$k$ primo {data-toc-label=“k primo”}

Consideremos primero el caso de $k$ primo. La expresión explícita del factorial

$$n! = 1 \cdot 2 \cdot 3 \ldots (n-1) \cdot n$$

Nótese que cada $k$-ésimo elemento del producto es divisible por $k$, es decir, suma $+1$ a la respuesta; la cantidad de tales elementos es $\Bigl\lfloor\dfrac{n}{k}\Bigr\rfloor$.

Luego, cada $k^2$-ésimo elemento es divisible por $k^2$, es decir, suma otro $+1$ a la respuesta (la primera potencia de $k$ ya se contó en el párrafo anterior). La cantidad de tales elementos es $\Bigl\lfloor\dfrac{n}{k^2}\Bigr\rfloor$.

Y así sucesivamente, para cada $i$ cada $k^i$-ésimo elemento suma otro $+1$ a la respuesta, y hay $\Bigl\lfloor\dfrac{n}{k^i}\Bigr\rfloor$ de esos elementos.

La respuesta final es

$$\Bigl\lfloor\dfrac{n}{k}\Bigr\rfloor + \Bigl\lfloor\dfrac{n}{k^2}\Bigr\rfloor + \ldots + \Bigl\lfloor\dfrac{n}{k^i}\Bigr\rfloor + \ldots$$

Este resultado también se conoce como fórmula de Legendre . La suma es por supuesto finita, ya que solo aproximadamente los primeros $\log_k n$ elementos no son ceros. Así, el tiempo de ejecución de este algoritmo es $O(\log_k n)$.

Implementación

 
int fact_pow (int n, int k) {
	int res = 0;
	while (n) {
		n /= k;
		res += n;
	}
	return res;
}
 

$k$ compuesto {data-toc-label=“k compuesto”}

La misma idea no se puede aplicar de forma directa. En su lugar podemos factorizar $k$, representándolo como $k = k_1^{p_1} \cdot \ldots \cdot k_m^{p_m}$. Para cada $k_i$, hallamos la cantidad de veces que está presente en $n!$ usando el algoritmo descrito arriba; llamemos a este valor $a_i$. La respuesta para $k$ compuesto será

$$\min_ {i=1 \ldots m} \dfrac{a_i}{p_i}$$