Algoritmos e Estruturas de Dados

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 . Se chegarmos a um ponto em que o divisor seja maior do que , 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 .
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:
n = 24
  1. p = 2, n = 24 (aumentámos p de 1 para 2 no início do ciclo) n % 2 == 0 ⇒ divisors = [2], powers = [0] n //= 2 ⇒ n = 12, powers = [1] n //= 2 ⇒ n = 6, powers = [2] n //= 2 ⇒ n = 3, powers = [3]
  1. p = 3, n = 3 ⇒ parar o ciclo while pois p * p = 9 é maior que 2
  1. n > 1 ⇒ divisors = [2, 3], powers = [3, 1]
n = 75
  1. p = 2, n = 75
  1. p = 3, n = 75 n % 3 == 0 ⇒ divisors = [3], powers = [0] n //= 3 ⇒ n = 25, powers = [1]
  1. p = 4, n = 25
  1. p = 5, n = 25 n % 5 == 0 ⇒ divisors = [3, 5], powers = [1, 0] n //= 5 ⇒ n = 5, powers = [1, 1] n //= 5 ⇒ n = 1, powers = [1, 2]
  1. p * p > n ⇒ parar o ciclo while ⇒ divisors = [3, 5], powers = [1, 2]
n = 84
  1. p = 2, n = 84 n % 2 == 0 ⇒ divisors = [2], powers = [0] n //= 2 ⇒ n = 42, powers = [1] n //= 2 ⇒ n = 21, powers = [2]
  1. p = 3, n = 21 n % 3 == 0 ⇒ divisors = [2, 3], powers = [2, 0] n //= 3 ⇒ n = 7, powers = [2, 1]
  1. p * p > n ⇒ parar o ciclo while
  1. n > 1 ⇒ divisors = [2, 3, 7], powers = [2, 1, 1]
n = 31
  1. p = 2, n = 31
  1. p = 3, n = 31
  1. p = 4, n = 31
  1. p = 5, n = 31
  1. p = 6, n = 31
  1. p * p > n ⇒ parar o ciclo while
  1. n > 1 ⇒ divisors = [31], powers = [1]

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 ≤ ).

Saída

O programa deve imprimir o maior fator primo de n.

Exemplos

Entrada
Saída
8
2
24
3
75
5
31
31
Bónus: Por que não verificamos apenas números primos?
Na nossa implementação atual, percorremos todos os números 2, 3, 4, … até . À primeira vista, poderia parecer mais lógico iterar apenas sobre números primos. De facto, pode haver casos em que isso funcione bem. No entanto, gerar todos os números primos até exige mais iterações do que simplesmente verificar se n é divisível por cada inteiro até (mais precisamente, o procedimento demandaria algo em torno de para gerar esses primos).
Consegue pensar num cenário em que pré-calcular todos os números primos até certo valor e depois utilizá-los para extrair os fatores primos pudesse ser mais eficiente?
 
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue