Fórmula de Legendre

A fórmula de Legendre encontra 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 cálculo termina quando o denominador ultrapassa o numerador.

Para ilustrar:

int p = 5;
int n = 100;

n / p + n / (p * p)
// Não inclua n / (p * p * p), porque 125 > 100.

int p = 2;
int n = 128;

n / p + n / (p * p) + n / (p * p * p)
// Continue até n / 128.

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

Exemplos

Program.legendre(5, 100) ➞ 24

Program.legendre(2, 128) ➞ 127

Program.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.