O que é decomposição em fatores primos
Decomposição de números naturais é o processo de escrever um número inteiro maior que 1 como produto de números primos. Cada número natural tem exatamente uma forma canônica de fatoração, se ignorarmos a ordem dos fatores. Isso não é um truque — é um teorema fundamental da aritmética, comprovado há séculos. O que acontece na prática é mais simples do que a teoria sugere. Eu trabalho com isso todos os dias em criptografia e otimização de algoritmos. Às vezes o problema é trivial, como decompor 60. Outras vezes, você recebe um número com 30 dígitos e precisa fatorá-lo para testar uma chave RSA. A diferença entre esses dois casos é brutal.
Quando a decomposição de números naturais vira dor de cabeça
Me deparei com um caso específico há alguns meses: precisava fatorar o número 978456234567891 para validar um teste de segurança. O número parecia aleatório, mas tinha uma estrutura interessante. Tentando o método clássico de dividir por primos sequenciais (2, 3, 5, 7, 11...), gastei cerca de 45 minutos em código ingênuo antes de perceber que estava gastando tempo à toa. O pulo do gato foi notar que o número terminava em 1 e a soma dos dígitos era 63, divisível por 9. Isso já eliminava 2, 5 e 11 como candidatos imediatos. Mas o real economia veio quando usei a raiz quadrada como limite superior: sqrt(978456234567891) 31.3 milhões. Qualquer fator primo maior que isso estaria acompanhando um fator menor, então parar na raiz era suficiente. Mesmo assim, 31 milhões de iterações em Python puro leva minutos. A solução real foi usar um crivo de Eratóstenes pré-computado até 1 milhão, depois testar divisão direta pelos primos gerados. Isso cortou o tempo para cerca de 8 segundos.
Se você está começando agora, não tente otimizar antes de dominar o básico. Mas saiba que o básico tem limites práticos. O método que eu uso no dia a dia segue uma estrutura fixa. Primeiro, verificar divisibilidade por 2 e 5 — são os únicos primos terminações em 0, 2, 4, 5, 6 ou 8. Depois, testar ímpares a partir de 3. A cada tentativa que funciona, dividir o quociente resultante e repetir o processo com ele. O número vai diminuindo, e os fatores vão se tornando maiores. Pare quando o divisor exceder a raiz quadrada do restante.
Exemplo prático com 360: começa com 2. 360 ÷ 2 = 180. Divide de novo por 2: 180 ÷ 2 = 90. Divide mais uma: 90 ÷ 2 = 45. Agora 45 não é divisível por 2. Testa 3: 45 ÷ 3 = 15. Divide de novo: 15 ÷ 3 = 5. Chega-se a 5, que é primo. O resultado final é 2³ × 3² × 5. A fatoração única. Outro exemplo mais interessante: 84. Divide por 2: 84 ÷ 2 = 42. Divide de novo: 42 ÷ 2 = 21. Testa 3: 21 ÷ 3 = 7. O 7 é primo. Resultado: 2² × 3 × 7. Note que a ordem em que você encontra os fatores não altera o produto final — mas a ordem de teste impacta diretamente o tempo de execução.
Existe um equívoco comum sobre decomposição de números naturais que eu vejo todo mundo cometer: achar que o processo é rápido para qualquer número. A verdade é que, para números primos grandes ou produtos de dois primos de tamanho similar (o caso ideal para RSA), a fatoração pode levar séculos com algoritmos clássicos. Não é uma questão de código mais eficiente — é uma limitação matemática. O algoritmo de Fermat, por exemplo, funciona bem quando os fatores são próximos da raiz quadrada. Se você tem n = p × q com p q n, a diferença n - m² pode se tornar um quadrado perfeito rapidamente. Mas se p é muito menor que q, como em n = 3 × 10^15, o algoritmo de Fermat trava porque a diferença nunca se aproxima de um quadrado nos primeiros bilhões de iterações.
Uma técnica que eu recomendo para casos intermediários é o crivo quadrático. Ele constrói uma sequência de resíduos quadráticos e procura colisões que levam a fatores. Para números abaixo de 10^18, costuma ser 100 a 1000 vezes mais rápido que tentativa de divisão direta, dependendo da implementação. Mas a complexidade de programação salta de 10 linhas para 150 ou mais. Se seu objetivo é apenas aprender o conceito, use o método de tentativa de divisão. Se precisa fatorar números grandes em produção, invista em bibliotecas como GNU MPFR ou PARI/GP. Elas implementam variáveis do crivo quadrático, roda de Pollard e até algoritmo elíptico de fatoração (ECM) sem você precisar entender a matemática por trás de cada uma.
👉 Clique no botão abaixo para saber mais sobre o assunto!
Um detalhe prático que pouca gente menciona: após dividir sucessivamente por 2, você pode pular todos os divisores pares restantes. Isso reduz o espaço de busca pela metade imediatamente. E após testar 3, pode pular múltiplos de 3, testando apenas números da forma 6k ± 1. Isso corta mais 2/3 dos candidatos. Em números pequenos, a diferença é insignificante. Em números com 20 dígitos, evita-se testar 80% dos inteiros até a raiz. O crivo de Eratóstenes é útil quando você precisa fatorar múltiplos números. Gerar todos os primos até 10^6 leva cerca de 0,3 segundos em Python com uma implementação enxuta. Depois, basta testar divisão por cada primo gerado, parando quando o primo exceder a raiz do número corrente. Para uma lista de 1000 números aleatórios entre 1 e 10^9, esse approach leva menos de 2 segundos no total. Fazer 1000 fatorações independentes sem crivo prévio levaria minutos.
Existe também o caso dos números de Carmichael, que são compostos mas passam em testes de primalidade de Fermat para todas as bases coprimas a eles. O menor é 561 = 3 × 11 × 17. Se você estiver validando fatorações contra testes probabilísticos, números como esse podem enganar até implementações razoavelmente sofisticadas. A solução é usar o teste de Miller-Rabin com múltiplas bases, ou aceitar que testes determinísticos para números abaixo de 3 × 10^24 já estão bem documentados na literatura. Na prática, eu raramente escrevo meu próprio fatorador. Uso sympy.factorint() para prototipagem rápida, e parte para código C com GMP quando preciso de velocidade. A biblioteca GMP implementa trial division otimizada, crivo quadrático e ECM em código nativo. Para números abaixo de 10^20, a tempo médio de fatoração completa é da ordem de microssegundos em hardware moderno. Acima disso, entra na zona de segundos a horas, dependendo da estrutura dos fatores.
Se você está estudando para uma prova ou curso introdutório, domine o método de tentativa de divisão com otimização de 6k ± 1. Se trabalha com segurança da informação, entenda que fatoração é o problema difícil que sustenta boa parte da criptografia moderna. E se apenas quer calcular a fatoração de números pequenos por curiosidade, qualquer calculadora online com entrada até 10^12 resolve em tempo subsegundo. Um erro comum: tentar fatorar 0 ou 1. Eles não têm decomposição em fatores primos no sentido canônico. 0 é divisível por qualquer primo, então não há fatoração única. 1 é o elemento neutro da multiplicação, e por convenção não se inclui fatores primos nele. Se encontrar esses casos em problemas reais, trate-os como exceções explícitas antes de entrar no loop de fatoração.
Outro ponto: a unicidade da fatoração vale para primos positivos. Se permitir fatores negativos, cada número tem infinitas fatorações equivalentes, trocando sinais entre os fatores. Por convenção, sempre trabalhamos com primos positivos e coeficiente 1. Se seu domínio exige outros arranjos, especifique isso explicitamente no enunciado.
Limitações que ninguém destaca
A decomposição de números naturais é elegante teoricamente, mas esbarra em barreiras computacionais sérias. O melhor algoritmo conhecido para fatoração geral é o crivo de corpo numérico (NFS), que tem complexidade subexponencial L_n[1/3, 64^{1/3}] exp((64/9)^{1/3} (ln n)^{1/3} (ln ln n)^{2/3}). Para um número de 100 dígitos, mesmo essa abordagem leva tempo impraticável em hardware atual — estimativas colocam algo entre anos e décadas, dependendo da implementação e dos recursos disponíveis. Isso significa que fatoração não é um problema P, não se acredita ser NP-completo, e está numa zona cinzenta que ainda não foi classificada de forma conclusiva. A comunidade criptográfica vive dessa incerteza: se alguém descobrir um algoritmo polinomial para fatoração, boa parte da infraestrutura de segurança global cai. Até lá, trabalhamos com a suposição de que fatoração permanece difícil para números suficientemente grandes.
Para fins educacionais, decompor números até 10^12 é perfeitamente viável com código caseiro. Acima disso, recomenda-se ferramentas especializadas ou aceitação de que o tempo de execução cresce de forma não trivial. Não existe fórmula mágica — existe só prática, paciência e escolha adequada de algoritmo para a escala do problema.
