O que é um número primo e como testar se um número é primo na prática
Primeiro deixa eu te mostrar o método que eu uso no dia a dia, porque a definição que todo mundo decora em escola não ajuda muito quando você precisa trabalhar com números grandes. Para testar se um número é primo, você divide ele pelos números primos menores ou iguais à raiz quadrada dele. Se nenhuma divisão resultar em resto zero, o número é primo. O resto é que importa, não o quociente. Se sobrar algo em qualquer divisão, o número não é divisível por aquele candidato e você continua tentando com o próximo primo. Eu trabalhei anos com criptografia e algoritmos de fatoração, e já passei sufoco com números que pareciam primos mas não eram. Um caso que ficou gravado na memória foi com o número 1.000.000.007. Todo mundo acha que é primo de cara porque o teste de divisão até a raiz quadrada dá certo — a raiz quadrada é aproximadamente 31.622, então você testa todos os primos até lá. Eu já tinha um script rodando pra isso, mas num projeto real percebi que estava gastando tempo demais com números compostos grandes que passavam por testes de primalidade rápidos de forma equivocada porque minha tabela de primos até 31.622 estava truncada em um ponto crítico. A correção foi simples: gerar a tabela de primos com o crivo de Eratóstenes antes de qualquer teste, e não confiar em uma lista prévia que eu podia ter cortado errado. Esse detalhe economizou horas de debugging.
O que um numero primo realmente significa
Um número primo é aquele que tem exatamente dois divisores positivos distintos: o número um e ele mesmo. O número 2 é primo, e é o único primo par. O número 1 não é primo, e esse é o erro mais comum que eu vejo gente cometendo. Se você tratar 1 como primo em qualquer algoritmo de fatoração, vai dar errado desde o começo. O número 9 não é primo porque é divisível por 3. O número 15 não é primo porque é divisível por 3 e por 5. O teste de primalidade nada mais é do que verificar se existe algum divisor além de 1 e do próprio número. O que os livros costumam não explicar direito é que existem diferentes tipos de teste de primalidade e cada um tem seu uso prático. O teste de divisibilidade por tentativa é suficiente para números pequenos, digamos até 10^9 ou pouco mais. Para números maiores, como os usados em RSA, você precisa de testes probabilísticos como Miller-Rabin ou testes determinísticos como AKS. O teste de Miller-Rabin é o que eu recomendo na maioria dos casos — é rápido, confiável na prática, e roda em milissegundos até para números com dezenas de dígitos. O AKS é determinístico e rápido em teoria, mas na prática é mais lento que Miller-Rabin para a maioria dos tamanhos de número que você vai encontrar no mundo real.
👉 Clique no botão abaixo para saber mais sobre o assunto!
Outro ponto que pouca gente leva a sério é o crivo de Eratóstenes. Se você precisa saber quais primos existem num intervalo, o crivo é imbatível. Para números até 10 milhões, ele roda em menos de um segundo na maior parte das implementações razoáveis. Para números acima de 10^12, o crivo segmentado entra em jogo, mas aí você começa a precisar de otimizações de memória que só fazem sentido se o problema realmente exigir. Eu já vi gente tentar aplicar Miller-Rabin para gerar primos em lotes grandes, o que é perfeitamente viável, mas muito mais lento do que simplesmente rodar um crivo e coletar os primos da lista gerada. Números primos também aparecem em lugares que não são óbvios. Hashing, numeração de hash tables, geração de sequências pseudoaleatórias, algoritmos de compressão. Se você está construindo uma tabela hash e precisa de uma função de hash que distribua bem, escolher uma boa tamanho de tabela que seja primo ajuda a evitar colisões em padrões periódicos. Eu já corrigi um bug numa API de cache onde o problema era uma tabela hash cujo tamanho era potência de 2, e as chaves tinham um padrão que fazia com que 80% delas caíssem nos mesmos buckets. Mudar o tamanho da tabela para o primo mais próximo resolveu em dez minutos. A lição é: números primos não são só teoria, eles têm custo real quando você ignora sua existência.
Se você quer aprender a reconhecer primos rapidamente de cabeça, um truço útil é memorizar os primeiros 25 primos. Isso cobre qualquer cálculo manual que você fizer no dia a dia. Depois, quando começar a lidar com números maiores, pratique rodar o crivo de Eratóstenes no papel para intervalos de 100 em 100. Você vai entender na prática por que o teste de divisibilidade até a raiz quadrada funciona, e vai ganhar intuição sobre a densidade dos primos. Números primos ficam mais raros conforme você sobe, mas nunca desaparecem. Esse é um resultado que Euclides provou há mais de dois mil anos, e continua sendo verdade até hoje.
