Teste de divisibilidade pelo sqrt(n)
A forma prática de saber se um número é primo é tentar dividi-lo por todos os números primos até a raiz quadrada dele. Se nenhum dividir exatamente, o número é primo. Pronto. Não tem mágica. O motivo da raiz quadrada é simples: se um número composto tem um fator maior que sua raiz quadrada, ele obrigatoriamente tem outro fator menor que a raiz quadrada também. Então testar além disso é perda de tempo.
O método na prática
Para testar 97, por exemplo, você calcula sqrt(97) 9,8. Testa divisibilidade por 2, 3, 5 e 7. Nenhum divide 97. Logo, 97 é primo. Simples. Para números maiores, como 104729, a raiz quadrada dá cerca de 323. Você ainda testaria os primos até 323. Manualmente isso é inviável para quem não tá acostumado, mas com uma script em Python leva menos de meio segundo.
como identificar numeros primos rapidamente
Aqui vai um script bem direto: def e_primo(n):
if n < 2: return False
if n in (2, 3): return True
if n % 2 == 0 or n % 3 == 0: return False
i = 5
while i * i <= n:
if n % i == 0 or n % (i + 2) == 0:
return False
i += 6
return True
Esse código usa a otimização de testar apenas na forma 6k±1, pulando múltiplos de 2 e 3 de uma vez. O ganho é real: em vez de testar 161 divisores para um número próximo de 323, você testa cerca de 54. Para números de 15 algarismos, essa diferença é entre esperar alguns segundos e esperar vários minutos.
👉 Clique no botão abaixo para saber mais sobre o assunto!
Quando isso falha
Testar divisibilidade até sqrt(n) funciona perfeitamente para números que cabem em inteiros de 64 bits. Porém, quando você precisa testar números com 50, 100 ou mais dígitos, como se usa em criptografia RSA, o método direto vira um pesadelo. Pior: mesmo com otimizações, testar todos os possíveis divisores é computacionalmente proibitivo nesses tamanhos. Nesses casos, usamos testes probabilísticos como Miller-Rabin. Eles não provam com 100% de certeza absoluta (embora o risco de erro possa ser tornado arbitrariamente pequeno), mas rodam em tempo polinomial. Um teste de Miller-Rabin com 40 rodadas em um número de 300 dígitos leva microssegundos e tem probabilidade de erro inferior a 4^(-40), que é basicamente zero na prática.
Eu já perdi tempo quebrando a cabeça com isso anos atrás. Tinha um colega que tava construindo um gerador de chaves RSA didático e o algoritmo de trial division travava em números grandes de forma silenciosa. O servidor não dava erro, simplesmente ficava hang. A solução foi trocar para Miller-Rabin com sementes fixas, que no caso de números abaixo de 3,3×10^18, é determinístico se usar os primos 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 e 37 como bases.
Pegadinhas comuns
1. O número 1 não é primo. Muita gente esquece e começa o teste a partir do 1. 2. 2 é o único primo par. Depois disso, todos os primos são ímpares. Se o número for par e maior que 2, já descarta na hora.
3. A crivo de Eratóstenes é útil quando você quer listar todos os primos até um limite N, mas não serve para testar um único número grande de forma eficiente. Ela consume memória proporcional a N. 4. Números perfeitos, amigáveis e outros conceitos parecidos não têm relação direta com primalidade no sentido prático. Não confunda.
Resumo sem rodeios
Para números pequenos até uns 10^12, trial division otimizada com passo 6k±1 resolve. Para números maiores, use Miller-Rabin com bases fixas para determinismo nas faixas conhecidas. Para números extremamente grandes sem conhecer fatores, o melhor que temos são testes probabilísticos — a fatoração completa de números grandes permanece um problema abertamente difícil, e é exatamente por isso que a criptografia de chave pública existe.
