Fórmula de Legendre

A fórmula de Legendre encontra o expoente da maior potência de algum número primo p que divide (é um fator de) o fatorial de algum 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 muitas frações (arredondadas para baixo), com n como numerador e uma potência de p progressivamente maior como denominador, parando quando o denominador excede o numerador.

Para ilustrar:

p = 5
n = 100

int(100/5) + int(100/25)
# No 100/125 because 125 > 100.

p = 2
n = 128

int(128/2) + int(128/4) + int(128/8) + ... + int(128/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 inteiros positivos.
• Quando p excede n, o resultado deve ser 0.