Fórmula de Legendre

La fórmula de Legendre encuentra el exponente de la mayor potencia de un número primo p que divide (es factor de) el factorial de un número n.

Ejemplo de la fórmula de Legendre (p = 2 y n = 27):

Por lo tanto, 2^23 es la mayor potencia de 2 que divide a 27!.

La fórmula devuelve la suma de varias fracciones (redondeadas hacia abajo), con n como numerador y una potencia cada vez mayor de p como denominador. El cálculo se detiene cuando el denominador supera al numerador.

Para ilustrarlo:

int p = 5;
int n = 100;

n / p + n / (p * p)
// No incluyas n / (p * p * p), porque 125 > 100.

int p = 2;
int n = 128;

n / p + n / (p * p) + n / (p * p * p)
// Continúa hasta n / 128.

Dados p y n, devuelve el resultado de la fórmula de Legendre (consulta Recursos).

Ejemplos

Program.legendre(5, 100) ➞ 24

Program.legendre(2, 128) ➞ 127

Program.legendre(3, 50) ➞ 22

Notas

• p y n serán enteros positivos.
• Cuando p sea mayor que n, el resultado debe ser 0.