Fatorização em primos

Qualquer inteiro positivo n ≥ 2 pode ser representado como um produto de números primos:

Existem muitas aplicações para encontrar os fatores primos de um número. É possível, por exemplo, calcular mais facilmente o número de divisores de um determinado valor, além de obter uma noção clara sobre o máximo divisor comum (GCD) e o mínimo múltiplo comum (LCM) de dois números, entre outras utilidades.

Para representar um número n (por exemplo, 300) como o produto dos seus fatores primos, podemos começar pelo menor número primo p (2) e, caso n seja divisível por p, continuar a dividi-lo por p enquanto for possível (300 / 2 = 150, 150 / 2 = 75).

Em seguida, aumenta-se p em 1 (p = 3) e volta-se a tentar dividir n por este novo valor. Caso seja divisível, dividimos n por p enquanto isso for possível (75 / 3 = 25).

Depois voltamos a aumentar p em 1 (p = 4) e tentamos dividir n por p. Note que não é possível dividir n por números que não são primos, pois n já foi exaustivamente dividido pelos primos menores que 4. No nosso exemplo, 300 é divisível por 4, mas 75 não o é, pois já extraímos todos os fatores 2 de 300 anteriormente. Portanto, se todos os 2s já foram retirados, números como 4, 6, 8 (múltiplos de 2) não irão mais dividir o valor restante. Como seguimos esse processo do menor para o maior número, podemos ter certeza de que só restarão números primos para dividir o valor ainda não decomposto.

No passo seguinte, aumentamos o divisor em 1 novamente (p = 5) e tentamos dividir n pelo novo p (75 / 5 = 5, 5 / 5 = 1). Continuamos assim até que o divisor seja maior do que $\sqrt{n}$. Se chegarmos a um ponto em que o divisor seja maior do que $\sqrt{n}$, significa que a parte restante de n é um número primo e podemos incluí-lo diretamente na nossa lista de divisores.

Dessa forma, no exemplo dado, 300 pode ser representado como $2 \cdot 2 \cdot 3 \cdot 5 \cdot 5$.

n = ...                              # Representar n como um produto de primos
p, divisors, powers = 1, [], []      # fator primo, divisores e seus expoentes

while p * p <= n:                    # enquanto p <= sqrt(n)
    p += 1                           # adiciona 1 ao fator primo a cada iteração
    if n % p != 0:                   # não faz nada se n não for divisível por p
        continue
    
    divisors.append(p)               # n % p == 0 => adicionar p como fator primo
    powers.append(0)                 # o expoente começa em 0
    while n % p == 0:                # dividir o máximo de vezes possível
        n //= p
        powers[-1] += 1              # aumentar o expoente em 1 a cada divisão

if n > 1:                            # se p > sqrt(n) => n ainda é um fator primo
    divisors.append(n)               # adicionar n como divisor
    powers.append(1)                 # com expoente igual a 1

print(list(zip(divisors, powers)))   # imprimir fatores e seus expoentes

A cada iteração do algoritmo, dividimos o número pelo seu fator primo se for possível, aumentando simultaneamente o expoente a cada divisão realizada.

Vamos agora simular o algoritmo em alguns números:

Desafio

Dado um inteiro n, pede-se para encontrar o seu maior fator primo.

Entrada

A primeira linha da entrada contém um único inteiro n (2 ≤ n ≤ $10^9$).

Saída

O programa deve imprimir o maior fator primo de n.

Exemplos