O que é um número primo na prática
Um número primo é aquele que só se divide exatamente por 1 e por ele mesmo. Parece simples, mas a parte chata é que essa simplicidade esconde uma série de armadilhas que as pessoas descobrem tarde demais. Quando eu comecei a mexer com criptografia RSA nos primeiros projetos da faculdade, gastei dias inteiros tentando entender por que meu código não encontrava primos grandes o suficiente. O problema não era a teoria — era a implementação. Para entender oque e numero primo de verdade, você precisa ver isso do ponto de quem realmente precisa calcular esses números, não do ponto de vista da teoria dos números pura. Na prática, um primo é qualquer inteiro maior que 1 que não tem divisores além de 1 e dele mesmo. O dois é primo. O três é primo. O quatro não é, porque 2 x 2 = 4. O cinco é primo. O seis não é, porque 2 x 3 = 6. A sequência começa assim: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47... e segue indefinidamente.
Como testar se um número é primo de forma eficiente
O método ingênuo que todo mundo aprende primeiro é tentar dividir o número por tudo até a metade dele. Isso funciona para números pequenos, mas para primos grandes isso é inviável. Se você precisa testar um número como 999983, fazer divisões até 499991 é um absurdo computacional. O que funciona de verdade é testar divisores apenas até a raiz quadrada do número. Se N não tiver nenhum divisor menor ou igual a sqrt(N), então N é primo. Isso reduz drasticamente o número de operações. Para o 999983, em vez de 499991 divisões, você faz cerca de 1000. A diferença é enorme.
Aqui vai um exemplo concreto do que eu uso no dia a dia: Passo 1: Se o número for menor que 2, não é primo. Pronto.
Passo 2: Se for igual a 2, é primo. É o único primo par. Passo 3: Se for par e maior que 2, não é primo. Você já eliminou metade dos candidatos.
Passo 4: A partir daí, teste apenas os ímpares de 3 até a raiz quadrada. Se nenhum dividir exatamente, o número é primo. Um detalhe que quase ninguém menciona: depois de testar a divisibilidade por 2 e 3, você pode usar um truque chamado "trial division por primos de forma otimizada". Todos os primos maiores que 3 são da forma 6k ± 1. Isso significa que, em vez de testar todos os números ímpares, você testa apenas 5, 7, 11, 13, 17, 19... pulando múltiplos de 2 e 3. Corta cerca de dois terços dos testes em relação ao método ingênuo de testar tudo.
👉 Clique no botão abaixo para saber mais sobre o assunto!
O erro que eu cometi e como resolver
Num projeto real de geração de chaves RSA, eu precisei gerar primos de 1024 bits. A abordagem inicial foi usar trial division convencional, e o código simplesmente travava. Testar divisores até a raiz quadrada de um número de 1024 bits seria impossível na prática — a raiz quadrada ainda seria um número colossal. A solução foi abandonar o trial division e partir para o teste de Miller-Rabin. Esse é um teste probabilístico que, com várias iterações, praticamente elimina falsos positivos. Com 20 rodadas, a chance de um composto passar como primo é menor que 1 em 4^20, o que é desprezível para a maioria das aplicações. Eu configurei o gerador para produzir um número aleatório ímpar de 1024 bits, aplicar Miller-Rabin com 20 rodadas, e se passasse, considerar primo. Isso reduziu o tempo de geração de algo como minutos para milissegundos em cada tentativa.
Se você precisa apenas de primos pequenos para estudo ou projetos simples, o trial division otimizado por 6k ± 1 resolve. Mas para criptografia, números grandes são obrigatórios e aí você precisa de testes probabilísticos ou de tabelas pré-computadas.
Limitações que ninguém conta
Teste de Miller-Rabin tem um defeito que poucos mencionam: existem chamados pseudoprimos de Miller-Rabin para bases específicas. Numbers como o 2047 são compósitos, mas passam no teste com base 2. Por isso nunca se deve rodar apenas uma iteração. Com múltiplas bases aleatórias, o risco cai exponencialmente. O problema é que cada iteração adicional custa tempo, e em sistemas embarcados com recursos limitados isso pode ser um gargalo real. Outro ponto: a distribuição dos primos não é uniforme. Conforme os números crescem, eles ficam mais rarefeitos. Entre 1 e 1 milhão há 78.498 primos. Entre 100 milhões e 101 milhões, há 5.761. Isso significa que, para gerar um primo grande, você provavelmente vai precisar testar vários candidatos antes de encontrar um. Para primos de 1024 bits, em média você testa cerca de 710 números antes de achar um primo, segundo a função densidade primordial.
Se o seu objetivo é simplesmente listar primos até um limite (digamos, até 10 milhões), o crivo de Eratóstenes é insuperável. Ele marca os múltiplos de cada primo encontrado e sobram apenas os primos. É O(n log log n) em complexidade e roda em milissegundos para limites na faixa de milhões. Eu uso esse crivo quando preciso de uma lista completa de primos para testes de unidades, e o resultado costuma levar menos de 200ms no meu setup. Não existe uma solução perfeita para todos os cenários. Trial division funciona até uns 10^12, depois vira brinquedo. Miller-Rabin entra em cena para primos grandes em criptografia. O crivo de Eratóstenes é rei para listagens de faixas menores. Entender quando usar cada um faz mais diferença do que decorar a definição.
Se quiser implementar algo rápido, uma boa referência é a função `isPrime` do módulo `math` do Python combinada com Miller-Rabin, ou bibliotecas como `gmpy2` que já têm testes de primalidade otimizados em C. Para um projeto sério de criptografia, confie em bibliotecas estabelecidas como OpenSSL ou NaCl — escrever seu próprio gerador de primos em produção é uma das formas mais baratas de ter dor de cabeça.
