Como entender números primos e composto na prática
O assunto parece simples quando você lê a definição no livro didático, mas a aplicação real traz alguns pontos que costumam confundir as pessoas. Números primos e composto formam a base de muitas coisas, desde criptografia até algoritmos de otimização, então vale a pena entender como isso funciona de verdade. Um número primo é aquele que tem exatamente dois divisores positivos: ele mesmo e o número 1. O número 1 não conta como primo, apesar de parecer que sim à primeira vista. Isso é uma convenção antiga, mas importante, porque se o 1 fosse primo, a fatoração única deixaria de ser única.
Um número composto é qualquer inteiro maior que 1 que não é primo. Ou seja, tem pelo menos um divisor além de 1 e dele mesmo. O número 4 é composto porque é divisível por 2. O número 6 também é composto, com divisores 2 e 3.
O método de teste de divisibilidade para números pequenos
Para saber se um número pequeno é primo, o jeito mais direto é tentar dividir por todos os números ímpares a partir do 2 até a raiz quadrada dele. Se nenhum desses números dividir exatamente, o número é primo. Não precisa testar divisores maiores que a raiz quadrada porque, se um número maior que a raiz quadrada dividisse o original, o quociente seria menor que a raiz quadrada, e você já teria encontrado esse divisor menor antes. Por exemplo, para testar o número 97, você calcula a raiz quadrada, que dá aproximadamente 9,8. Você testa divisão por 2, 3, 5 e 7. Nenhum deles funciona. Conclusão: 97 é primo.
O problema é que esse método funciona bem apenas para números pequenos. Quando eu estava revisando parâmetros RSA para um projeto interno, precisei verificar se um número de 64 dígitos era primo. Tentar divisão por tentativa e erro até a raiz quadrada ia levar séculos computacionais. A solução foi usar o teste de Miller-Rabin, que é probabilístico mas extremamente confiável quando rodado com bases suficientes. Com 7 iterações, o erro cai para menos de 4 elevado a menos de 7, o que é mais que suficiente para uso prático.
O crivo de Eratóstenes
Se o objetivo é encontrar todos os primos até um certo limite, o crivo de Eratóstenes é a ferramenta padrão. A ideia é simple: você escreve todos os números de 2 até N, marca o 2 como primo e risca todos os múltiplos dele. Depois vai para o próximo número não riscado, que é o 3, e risca todos os múltiplos de 3. Repete até processar a raiz quadrada de N. Esse método tem complexidade O(N log log N), o que significa que para gerar todos os primos até 1 milhão, você leva frações de segundo em uma máquina moderna. Já para 1 bilhão, o tempo sobe para alguns segundos, dependendo da implementação e da memória disponível.
👉 Clique no botão abaixo para saber mais sobre o assunto!
Uma otimização que muita gente ignora: em vez de começar a riscar a partir de 2 vezes o número atual, comece a riscar a partir do quadrado dele. Todo múltiplo anterior já foi riscado por um divisor menor. Isso reduz o trabalho em cerca de metade na prática.
Pontos que ninguém explica direito
Muita gente acha que números primos são raros. Na verdade, a densidade deles é alta o suficiente para ser útil. O teorema dos números primos diz que a probabilidade de um número aleatório próximo de N ser primo é aproximadamente 1 sobre o logaritmo natural de N. Para números de 10 dígitos, isso dá cerca de 1 em 23. Para números de 100 dígitos, cerca de 1 em 230. Ainda há muitos primos por aí, mas a distribuição fica mais esparsa conforme o número cresce. Outro equívoco comum é achar que todo número ímpar maior que 1 é primo. Não é verdade. 9, 15, 21, 25, 27 são todos ímpares e compostos. O teste de paridade é apenas um filtro inicial, não uma prova de primalidade.
Também é importante saber que existem pares de primos gêmeos, que são dois primos cuja diferença é exatamente 2. Os pares conhecidos incluem (3,5), (5,7), (11,13), (17,19) e assim por diante. A conjectura dos primos gêmeos, que afirma que existem infinitos desses pares, ainda não foi provada. É um problema aberto na matemática.
Fatoração em números primos
Toda número composto pode ser escrito como produto de fatores primos. Essa é a decomposição em fatores primos, e ela é única para cada número. Por exemplo, 60 se decompõe em 2² × 3 × 5. Não existe outra combinação de primos que dê 60. Quando você precisa fatorar um número composto grande, o processo é bem mais trabalhoso do que testar primalidade. Fatorar um número de 30 dígitos em tempos razoáveis já exige algoritmos sofisticados como o crivo quadrático ou a curva elíptica de fatoração. Para números de 60 dígitos ou mais, até os melhores algoritmos levam tempo significativo, e é exatamente essa dificuldade que sustenta a segurança do RSA.
Uma dica prática: antes de tentar fatoração, verifique divisores pequenos primeiro. 2, 3, 5, 7, 11, 13. Se o número for divisível por algum deles, você já reduz o problema. Na maioria dos casos práticos, isso elimina a maior parte dos fatores rapidamente.
Quando tudo isso falha
O teste de primalidade por tentativa de divisão funciona até números de algumas centenas de milhões. Depois disso, o tempo explode. O crivo de Eratóstenes é eficiente para gerar primos em intervalo fechado, mas consome memória proporcional ao limite. Para números muito grandes, testes probabilísticos como Miller-Rabin são a escolha certa, mas eles não dão certeza absoluta sem uma verificação posterior. A fatoração de números grandes continua sendo um problema computacionalmente difícil, e não existe algoritmo conhecido que resolva isso de forma eficiente para qualquer tamanho de número. Se alguém descobrir um, boa parte da criptografia moderna precisa ser revista.
