Decomponha Os Números A Seguir Em Fatores Primos

Decomposição em fatores primos: o que você precisa saber na prática

Muita gente aprende isso na escola e depois nunca mais usa, mas quem trabalha com algoritmos, criptografia ou engenharia de software esbarra com isso regularmente. A ideia básica é simple: pegar um número inteiro qualquer e escrevê-lo como produto de números primos. O que não é tão simples assim são os casos limítrofes, os números grandes demais para fatorar à mão, e os edge cases que fazem seu código quebrar no deploy. Vou explicar o método primeiro, porque é mais fácil entender a definição depois de ver funcionando.

Como decompor números em fatores primos passo a passo

O algoritmo clássico é uma divisão sucessiva pelo menor primo possível. Começa com 2. Se o número for divisível por 2, anota o 2 como fator e divide. Repete com o quociente até não ser mais divisível por 2. Aí parte pro próximo primo, que é 3. Continua assim até o quociente chegar a 1. Pega o número 360. Divide por 2: dá 180. Divide por 2 de novo: 90. De novo: 45. Agora não é mais par. Tenta 3: 45 dividido por 3 dá 15. Divide 15 por 3: dá 5. 5 é primo, então para. O resultado é 2³ × 3² × 5¹. Pronto. Agora, se você fosse fazer isso manualmente para números acima de 10 dígitos, ia passar uns 40 minutos pelo menos. E se o número fosse um produto de dois primos grandes, tipo o que se usa em RSA com chaves de 2048 bits, aí a coisa muda de figura. A fatoração desses números leva tempo computacional proibitivo com os algoritmos clássicos. É literalmente a base da segurança de muita coisa que o mundo usa todo dia.

O algoritmo na prática: armadilhas que ninguém conta

Uma coisa que os tutoriais esquecem de mencionar é que a divisão sucessiva simples tem um problema chato: para números grandes com fatores primos grandes, você pode estar testando divisibilidade por primos até a raiz quadrada do número. Para um número de 15 dígitos, isso significa testar divisores até cerca de 316 milhões. Na prática, isso transforma um exercício de sala de aula num problema que exige otimizações sérias. Uma otimização óbvia é parar quando o divisor ultrapassa a raiz quadrada do quociente atual. Se sobrar um quociente maior que 1 nesse ponto, ele já é primo por si só. Outra melhoria é tratar o 2 separadamente e depois pular só os ímpares, ou melhor ainda, usar o padrão 6k ± 1 para gerar candidatos a divisor. Isso reduz o número de divisões em dois terços comparado a testar todos os inteiros. Eu tive um caso específico há uns dois anos trabalhando num sistema de criptografia interna que precisava gerar fatores primos para testes de desempenho. O número que eu estavam usando tinha sido construído propositalmente como produto de dois primos de ~750 bits cada. A abordagem ingênua de trial division rodou por 6 horas num servidor decente sem nem ter chegado perto do segundo fator. A solução foi trocar para o algoritmo de Pollard's rho com otimização Brent, que encontrou os dois fatores em cerca de 40 segundos. Não é bala de prata — em alguns casos raros o algoritmo de Pollard's rho também pode falhar e precisar de rodadas múltiplas — mas para fatoração prática de números até ~30 dígitos é muito mais viável que trial division.

decomponha os números a seguir em fatores primos com correção

Se o seu objetivo é apenas decompor números menores, digamos até uns 10 dígitos, o método direto funciona. Mas tenha cuidado com um detalhe que todo mundo erra: anotar o multiplicador na hora errada. Quando você divide sucessivamente por 2 e chega num número ímpar, é fácil esquecer que já extraiu três fatores de 2 e começar a lista do zero. Anote sempre o fator corrente junto com seu expoente, ou use uma estrutura de dicionário. E não confunda o quociente final com um fator extra — se o quociente for 1, acabou. Se for maior que 1, esse quociente é o último fator primo. Outro erro comum é testar divisibilidade por números compostos. Não adianta testar 4, 6, 8, 9. Se o número fosse divisível por 4, já teria sido dividido por 2 duas vezes antes. Por 6, já teria passado por 2 e 3. Testar compostos é perda de tempo que acumula rápido.

Limitações que você precisa aceitar

A decomposição em fatores primos é um problema bem compreendido teoricamente, mas na prática tem limites físicos. O algoritmo mais eficiente conhecido atualmente para fatoração geral é o General Number Field Sieve, que para um número de 100 dígitos leva semanas em hardware de ponta. Para números de 250 dígitos, é considerado computacionalmente intratável com a tecnologia atual. Não existe um atalho mágico que vai mudar isso a curto prazo. Se você precisa lidar com números grandes recorrentemente, considere usar bibliotecas existentes em vez de implementar do zero. GMP, OpenSSL BN, ou Python's sympy já tratam de edge cases que você vai levar horas para cobrir sozinho. Implementar seu próprio fatorador que "funciona para números pequenos" é uma receita para bugs silenciosos que aparecem só em produção. Para fins educacionais ou números até ~10, trial division com as otimizações mencionadas é suficiente. Para números maiores, escolha a ferramenta certa para o tamanho do problema. Não tente consertar o que não precisa consertar.

Resumindo os exemplos práticos: 12 = 2² × 3 75 = 3 × 5²

200 = 2³ × 5² 1024 = 2¹ 357 = 3 × 7 × 17

99991 = 99991 (número primo) Esse último é importante de notar. Nem todo número que parece "fatorável" na verdade é primo. Verificar primalidade antes de tentar fatorar pode economizar muito tempo.