Fórmula de Legendre

A fórmula de Legendre determina o expoente da maior potência de um número primo $p que divide (é fator de) o fatorial de um número $n.

Exemplo da fórmula de Legendre (p = 2 e n = 27):

Portanto, 2^23 é a maior potência de 2 que divide 27!.

A fórmula retorna a soma de várias frações (arredondadas para baixo), com $n como numerador e uma potência cada vez maior de $p como denominador. O processo termina quando o denominador ultrapassa o numerador.

Para ilustrar:

$p = 5;
$n = 100;

intdiv($n, $p) + intdiv($n, $p * $p);
// Não inclua intdiv($n, $p * $p * $p), pois 125 > 100.

$p = 2;
$n = 128;

intdiv($n, $p) + intdiv($n, $p * $p) + intdiv($n, $p * $p * $p);
// Continue até intdiv($n, 128).

Dados $p e $n, retorne o resultado da fórmula de Legendre (consulte Recursos).

Exemplos

legendre(5, 100) ➞ 24

legendre(2, 128) ➞ 127

legendre(3, 50) ➞ 22

Observações

• $p e $n serão números inteiros positivos.
• Quando $p for maior que $n, o resultado deverá ser 0.