Entendendo números primos e compostos na prática
A maioria das pessoas aprende a definição de número primo no ensino fundamental e acha que é coisa resolvida. Números primos só têm dois divisores: o 1 e ele mesmo. Números compostos têm mais de dois divisores. A teoria é simples. O problema aparece quando você precisa aplicar isso de verdade, especialmente em programação ou em cálculos que exigem fatoração. Eu já passei bastante tempo lidando com isso em projetos de criptografia e otimização de algoritmos, então vou explicar como isso funciona de fato, incluindo os detalhes que os livros didáticos geralmente pulam.
O que é numero primo e composto
Um número primo é um inteiro maior que 1 que não pode ser escrito como produto de dois inteiros menores que ele. O 2 é primo, o 3 é primo, o 5 é primo. Já um número composto é qualquer inteiro maior que 1 que não é primo. O 4 é composto porque é 2 vezes 2. O 6 é composto porque é 2 vezes 3. O 1 não é nem primo nem composto. Isso é importante porque muita gente esquece essa exceção e inclui o 1 na lista de primos por engano. Na prática, para testar se um número é primo, você não precisa verificar todos os divisores até o próprio número. Basta verificar divisores até a raiz quadrada dele. Se nenhum divisor for encontrado nesse intervalo, o número é primo. Isso reduz drasticamente o trabalho computacional.
Um caso específico que me deu trabalho foi ao processar uma lista de números grandes para gerar chaves RSA em um projeto interno. A função de teste de primalidade que estava usando testava divisibilidade até n-1, o que tornava o processo absurdamente lento para números acima de 10 dígitos. Troquei para um teste de Miller-Rabin, que é probabilístico mas extremamente rápido. Para números abaixo de 3.317.044.064.046.798.873.878.950.630.198.850.950.582.588.496.298.881, basta testar as bases 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 e 37 para ter certeza absoluta. Acima disso, usar várias rodadas de Miller-Rabin com bases aleatórias dá uma margem de erro tão pequena que é irrelevante para a maioria das aplicações práticas.
👉 Clique no botão abaixo para saber mais sobre o assunto!
Fatoração prima de números compostos
Todo número composto pode ser decomposto em fatores primos de forma única. Isso é o teorema fundamental da aritmética. Na prática, a fatoração é onde as coisas ficam difíceis. Para números pequenos, você fazTrial and error mesmo: divide pelo 2, depois pelo 3, pelo 5, e assim por diante. Para números maiores, o problema escala mal. Um número como 12.897.233 pode parecer gerenciável, mas a fatoração por tentativa direta exige testar divisores até cerca de 3.591. Isso é viável para um número, mas inviável para múltiplos números em produção. Aqui vai uma dica que eu aprendi na marra: quando for fatorar números compostos, use crivo de Eratóstenes para gerar os primos até um limite razoável antes de começar. Se você precisa fatorar vários números, calcular os primos de uma vez e reutilizá-los economiza muito tempo. No meu caso, eu costumo limitar o crivo a 1 milhão de primos, o que cobre fatoração de números até cerca de 10^12. Acima disso, aí sim entra necessidade de algoritmos mais pesados como o crivo quadrático ou a peneira de corpo numérico.
Pegadinhas comuns
Um erro frequente é achar que todos os números ímpares são primos. Claramente não é o caso. O 9, o 15, o 21, o 25 — todos são ímpares e compostos. Outro erro é confundir primo com número ímpar na hora de escrever código. Se sua função de teste de primalidade não trata o 2 como caso especial, ela pode falhar ou retornar resultados errados. Também é comum ver gente achando que 0 e negativos são primos ou compostos. Não são. A definição de primo se aplica apenas a inteiros positivos maiores que 1. O zero é um caso à parte, e números negativos nunca entram nessa discussão.
Quando usar cada conceito
Números primos são úteis em hashing, criptografia, geração de sequências pseudoaleatórias e em problemas de otimização onde a divisibilidade importa. Números compostos aparecem mais em fatoração, simplificação de frações, cálculo de MMC e MDC, e em problemas de teoria dos números aplicados. Se você está construindo um sistema que lida com divisibilidade ou decomposição, saber distinguir rapidamente entre primo e composto economiza ciclos de processamento e evita bugs sutis. Uma limitação que muitos não consideram é que o teste de primalidade determinístico (como o AKS) existe mas é muito lento na prática para números grandes. Por isso Miller-Rabin e outros testes probabilísticos são preferidos na maioria dos casos reais. A troca é clara: você ganha velocidade em troca de uma probabilidade infinitesimal de erro. Em praticamente todas as aplicações do mundo real, essa é uma troca mais do que aceitável.
