O que é decomposição de números
Decomposição de números, mais precisamente decomposição em fatores primos, é o processo de escrever um número inteiro positivo como o produto de números primos. Todo número maior que 1 pode ser escrito dessa forma de maneira única, exceto pela ordem dos fatores. Isso se chama Teorema Fundamental da Aritmética. Não tem mistério. O problema é que na prática as coisas ficam chatas rápido quando os números crescem.como fazer decomposicao de numeros na prática
Vamos ao método básico, que é divisão sucessiva por primos. Você pega o número, tenta dividir pelo menor primo possível, anota o divisor, continua com o quociente até chegar a 1. O conjunto de todos os divisores usados é a decomposição. Pegando 60 como exemplo:
60 dividido por 2 dá 30 30 dividido por 2 dá 15
15 dividido por 3 dá 5 5 dividido por 5 dá 1
Resultado: 60 = 2² × 3 × 5 A ordem dos primos na hora das divisões importa. Sempre comece por 2, depois 3, 5, 7, 11 e assim por diante. Pular primos é o erro mais comum. Já vi gente tentar dividir por 9 antes de testar 3, o que obviamente não funciona porque 9 não é primo. Isso acontece bastante em quem decora o processo sem entender o porquê.
Quando o método básico falha
A divisão sucessiva funciona perfeitamente para números pequenos e médios. Mas em números grandes, digamos acima de 10, o tempo cresce de forma absurda. O algoritmo de tentativa de divisão pela raiz quadrada do número tem complexidade O(n). Para um número de 18 dígitos, você estaria fazendo bilhões de divisões no pior caso. Na prática, isso significa horas ou dias dependendo da ferramenta. Eu me deparei com isso direto em um projeto de criptografia onde precisava decompor números gerados por funções de hash incompletas. Um deles era 999999999999999989, que parecia primo à primeira vista. A raiz quadrada é cerca de 1 bilhão. Tentar divisão sucessiva manual era inviável. A solução foi usar o teste de primalidade de Miller-Rabin primeiro para descartar compostos rapidamente, e só então aplicar o algoritmo de Pollard's rho para encontrar fatores. Com Pollard's rho, o tempo caiu de algo impraticável para segundos na maioria dos casos.
O teste de Miller-Rabin é probabilístico mas extremamente confiável com enough rodadas. Ele não te dá os fatores, só diz se o número provavelmente é primo ou composto. É um filtro essencial antes de gastar tempo tentando fatorar.
👉 Clique no botão abaixo para saber mais sobre o assunto!
Alternativas para números maiores
Além do Pollard's rho, existem outros algoritmos que valem conhecer dependendo do cenário: O crivo quadrático (quadratic sieve) é eficiente para números até cerca de 10¹. É o que a maioria das implementações práticas usa antes de migrar para métodos mais pesados.
O crivo do corpo de números (number field sieve) é o mais rápido conhecido para números acima de 10¹. É também o que torna a fatoração de chaves RSA grandes difícil na prática. Se um número é grande o suficiente para ser seguro contra o NFS, ele basicamente não é fatorável com tecnologia atual. Para quem só quer decompor números do dia a dia, uma planilha com a sequência de primos até 1000 e divisão manual resolve 99% dos casos. Não precisa de nada sofisticado.
Pegadinhas comuns
Não confunda decomposição com simplificação de frações ou MMC e MDC. São conceitos relacionados mas distintos. A decomposição é o passo intermediário que permite calcular os outros dois, mas ela em si é apenas a escrita do número como produto de primos. Também é comum errar na hora de verificar se parou no lugar certo. Se após dividir sucessivamente por 2, 3, 5, 7... o quociente restante for maior que 1 e não divisível por nenhum primo testado até sua raiz quadrada, esse resto já é primo. Não precisa continuar testando primos maiores que a raiz do número atual.
Outro detalhe: zero e um não têm decomposição em fatores primos. Zero é um caso especial que não se encaixa no teorema, e um é o elemento neutro da multiplicação. Se aparecer esses na sua lista de exercícios, trate como exceção.
Implementação rápida
Se precisar decompor vários números automaticamente, um script simples em Python faz o trabalho: def decompor(n): fatores = {} d = 2 while d * d <= n: while n % d == 0: fatores[d] = fatores.get(d, 0) + 1 n //= d d += 1 if n > 1: fatores[n] = fatores.get(n, 0) + 1 return fatores
Isso cobre divisões sucessivas otimizadas com o limite na raiz quadrada. Para números acima de 10¹², considere usar bibliotecas como sympy.factint() que implementam versões mais eficientes dos algoritmos mencionados. O site factordb.com é útil para consulta de fatores conhecidos. Milhões de números já foram fatorados pela comunidade e estão indexados. Antes de gastar tempo fatorando algo grande, dá uma olhada lá.
