Como identificar números primos na prática
Um número primo é aquele que só é divisível por 1 e por ele mesmo. Parece óbvio, mas a definição pura não te ajuda muito quando você precisa verificar isso rapidamente em uma calculadora ou num código que está travando. O importante é saber que a divisão tem que ser exata, sem resto, e só nesses dois casos. Se eu tiver que verificar se um número é primo, o método mais direto é o teste de divisão por tentativa. Você divide o número por todos os inteiros a partir de 2 até a raiz quadrada dele. Se nenhuma divisão der resto zero, o número é primo. Só isso. Não precisa de fórmula mágica.
Por exemplo, para testar o 13: a raiz quadrada é cerca de 3,6. Então você divide por 2 e por 3. 13 dividido por 2 dá resto 1. 13 dividido por 3 dá resto 1. Pronto, é primo. Para o 15: raiz quadrada perto de 3,87. Divide por 2, resto 1. Divide por 3, resto 0. Não é primo. Simples.
Lista de número primo de 1 a 20
Aqui estão os resultados. Do 1 ao 20, os primos são: 2, 3, 5, 7, 11, 13, 17 e 19. Isso dá oito números no total. O 1 não entra nessa lista porque, por definição moderna, primo precisa ter exatamente dois divisores distintos. O 1 tem apenas um. Esse é um erro comum de quem está começando e que já vi causar bug em código de criptografia amador várias vezes. O 2 é o único primo par. A partir daí, todos os outros primos são ímpares. Todo número par maior que 2 é divisível por 2, então automaticamente deixa de ser primo. Isso economiza muita verificação desnecessária.
👉 Clique no botão abaixo para saber mais sobre o assunto!
Tem um detalhe que poucas pessoas mencionam e que vale a pena saber. Quando você está verificando manualmente, pode pular os divisores pares depois do 2. Ou seja, depois de testar a divisibilidade por 2, você testa só por 3, 5, 7, 11... números ímpares. Isso corta pela metade o trabalho em casos maiores. Eu tive um problema real com isso há alguns anos. Estava validando chaves RSA pequenas para um sistema interno e percebi que o código de teste de primalidade estava levando 40 segundos para verificar números na casa dos milhares. O gargalo era que ele testava divisão por todos os números, inclusive pares acima de 2. A correção foi implementar um wheel factorization básico: testar 2 e 3 primeiro, depois pular de 6 em 6, testando só i e i+2 em cada iteração. O tempo caiu para 0,3 segundo. A diferença não é trivial.
Outro ponto que merece atenção: o teste por divisão por tentativa funciona bem até certa escala. Para números abaixo de 1 milhão, ainda é perfeitamente viável. Acima disso, começam a aparecer problemas de performance séria. Nesse caso, o teste de Miller-Rabin é o padrão da indústria. Ele é probabilístico, mas com o número certo de iterações a chance de erro fica tão baixa que praticamente não existe na prática. Um teste completo com 7 rounds de Miller-Rabin já é suficiente para a maioria das aplicações de segurança. Quem precisa apenas da lista de primos pequenos para estudar ou para uso didático não precisa de nada além disso aqui. Os oito números que citei acima são completos. Se você for programar, guarde eles em um array fixo e pronto. Não vale a pena rodar um algoritmo inteiro só para listar primos até 20. Isso é perder tempo.
A regra geral que funciona na prática: para números pequenos, use divisão por tentativa com otimização de pular pares e usar a raiz quadrada como limite. Para números grandes, migre para Miller-Rabin. Para listas fixas pequenas, codifique os valores diretamente. Cada caso tem sua solução, e usar a errado é só perder tempo.
