Números primos: o básico que ninguém explica direito
Um número primo é aquele que tem exatamente dois divisores naturais: ele mesmo e o um. Pronto. 2, 3, 5, 7, 11, 13, 17... a sequência para, mas os números não. 4 não é primo porque divide por 1, 2 e 4. 9 não é primo porque divide por 1, 3 e 9. Simples, mas a simplicidade enganosa é o que causa confusão depois. O que são números primos, na prática?
Na minha cabeça, sempre pensei neles como os blocos de construção dos inteiros. Todo número maior que 1 pode ser fatorado de um jeito único em primos. Isso se chama teorema fundamental da aritmética e é tão útil que parece trivial, mas não é. É profundo demais pra ser óbvio e é exatamente por isso que todo mundo usa e todo mundo ignora.
O que são números primos: definição prática
A definição formal é curta demais pra alguém entender de verdade sem ver funcionando. Um número natural p > 1 é primo se, e somente se, os únicos divisores positivos de p são 1 e p. O 1 não é primo por definição, mesmo que alguns textos mais antigos discutissem isso. Não discuta. O 1 não é primo e pronto. O 2 é o único primo par. Todo o resto é ímpar. Isso importa? Importa sim. Se você tentar usar uma fórmula que assume que todos os primos são ímpares sem verificar o 2, seu código quebra. Eu já vi isso acontecer em produção. Um sistema de geração de chaves RSA que ignorava o 2 como caso especial gerava pares de chaves ruins e o servidor entrava em loop de validação. Levou três horas pra gente descobrir. O log mostrava um número par sendo tratado como candidato a primo. Era o 2, óbvio. Remover o case especial do 2 resolveu.
Como encontrar primos na prática
O método mais conhecido é o crivo de Eratóstenes. Você marca todos os múltiplos de cada primo começando do 2. O que sobra não marcado é primo. Funciona bem até uns 10 milhões de números sem dor. Depois disso, o crivo gasta muita memória RAM e começa a ficar lento pra depender de como você implementa. Se você precisa de primos maiores que 10^9, o crivo simples não é a resposta. Aí você usa teste de primalidade probabilístico, tipo Miller-Rabin. Ele não prova que um número é primo de forma determinística, mas a chance de erro pode ser reduzida a algo ridículo, tipo 1 em 4^k onde k é o número de rodadas. Para fins práticos, se rodar Miller-Rabin com bases fixas pra números dentro de certo intervalo, vira teste determinístico. Pra números menores que 3,3×10^24, as bases 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 e 37 já são suficientes. Eu usei isso num projeto de criptografia há um tempo e funcionou perfeitamente, mas com um detalhe importante: a aritmética de BigInteger precisa ser bem feita. Uma multiplicação intermediária que transborde o tipo destrói o teste inteiro.
Exemplo rápido. Quer saber se 97 é primo? Você testa divisão só até a raiz quadrada, que aqui dá cerca de 9,8. Testa 2, 3, 5, 7. Nenhum divide. Conclusão: 97 é primo. Não precisa testar 8, 9 ou qualquer coisa acima de 9,8. Se tivesse divisores, um deles teria que ser menor ou igual à raiz. Essa é a observação mais subestimada sobre primos: você nunca precisa testar mais que até a raiz quadrada do número. Muitas pessoas testam até n/2 ou até n. Isso é perda de tempo enorme.
👉 Clique no botão abaixo para saber mais sobre o assunto!
Dicas que ninguém conta
Primeiro, não confie em funções de biblioteca que supostamente testam primalidade sem verificar a documentação. Algumas implementações antigas usam Fermat como teste único. Fermat tem falsos positivos chamados números de Carmichael. O menor é 561. 561 é composto, mas passa no teste de Fermat pra qualquer base coprima com ele. Se o seu código não lida com isso, ele diz que 561 é primo e ponto. Miller-Rabin com as bases certas evita esse problema. Segunda dica: memoize resultados de teste de primalidade. Se você já testou um número e ele foi primo, guarde. Se já testou e era composto, guarde também. Em projetos reais, números repetidos aparecem muito mais do que o esperado. Eu vi um servidor processar a mesma lista de candidatos centenas de vezes por hora. Adicionar um dicionário com cache reduziu o tempo de resposta de cerca de 4 segundos pra uns 200 milissegundos na carga típica.
Por que primos importam fora da matemática pura
Primologia pura é bonita, mas a utilidade real tá em criptografia, tabelas hash, geração de sequências pseudoaleatórias e algoritmos de fatoração. RSA depende de números primos grandes. Se você fosse bom em fatorar rapidamente, o RSA desaparecia. Ninguém sabe se isso é possível, mas ninguém provou que é impossível também. Esse é o problema aberto mais famoso que todo mundo conhece sem saber que conhece. Em tabelas hash, o tamanho da tabela como primo reduz colisões quando você usa operações lineares congruenciais. Em geradores de sequência, primos entram em fórmulas como o método do meio quadrado modificado. Não é mágica, é matemática aplicada com consequências diretas no desempenho.
Erros comuns e como evitar
Erro 1: achar que 1 é primo. Não é. Sempre trate 1 como caso especial. Erro 2: testar divisores até n em vez de até n. Erro 3: confiar em testes de primalidade que não lidam com números de Carmichael. Erro 4: usar primos pequenos demais pra RSA. Números de 8 dígitos são quebrados em segundos num laptop comum. Primos pra criptografia real precisam ter pelo menos 1024 bits, melhor ainda 2048 ou mais. Erro 5: esquecer que 2 é primo e par ao mesmo tempo. Se o seu algoritmo filtra primos descartando pares, você elimina o 2. Se o seu algoritmo assume que primos são ímpares, você pula validações importantes pro 2.
Limitações reais que eu vejo todo dia
O crivo de Eratóstenes gasta O(n) memória. Pra n = 10^9, isso dá cerca de 1 GB se usar um bit por número. Funciona, mas não cabe em todo lugar. Aí o crivo segmentado resolve dividindo o intervalo em blocos que cabem na memória. A desvantagem é que você precisa dos primos menores que a raiz do limite superior primeiro. Então o problema se transforma: primeiro você acha primos até N, depois aplica o crivo segmentado. Mais etapas, mais complexidade, mas cabe na RAM. Teste de primalidade determinístico completo, tipo AKS, existe e é polinomial. Na prática, é mais lento que Miller-Rabin pra números do tamanho que a gente usa no mundo real. Eu tentei implementar AKS num benchmark interno e Miller-Rabin com bases fixas foi dez vezes mais rápido com precisão idêntica pro intervalo que precisávamos. AKS é lindo teoricamente, mas bonito não paga conta. Use Miller-Rabin ou o teste determinístico baseado em bases fixas pro seu intervalo.
Outro problema: fatoração. Achamos primos fácil. Fatorar um composto grande em seus fatores primos é muito mais difícil. Não existe algoritmo conhecido que resolva isso em tempo polinomial. Esse desbalanço entre fácil verificar e difícil decompor é exatamente o que sustenta boa parte da criptografia moderna. Se alguém descobrir fatoração rápida, o mundo digital precisa se reconstruir. Por isso o assunto não morre.
Resumo prático
Definição: primo é número maior que 1 com exatamente dois divisores positivos. Teste de primalidade: divida até a raiz quadrada. Para números grandes: Miller-Rabin com bases fixas é suficiente e rápido. Crivo de Eratóstenes serve pra listas curtas. Crivo segmentado serve pra listas longas. 1 não é primo. 2 é primo. Números de Carmichael existem e quebram testes fracos. Primos são úteis fora da matemática pura em criptografia, hashing e aleatoriedade. Fatorar é difícil. Verificar é fácil. Essa assimetria é o que importa.
