Quais São Os Números Primos Menores Que 20

Encontrando primos sem complicar

Na prática, listar números primos menores que 20 é uma daquelas coisas que todo mundo aprende no ensino médio e depois esquece, mas aparecem o tempo todo quando você precisa de algo simples e rápido. A resposta direta é: 2, 3, 5, 7, 11, 13, 17 e 19. Apenas esses oito. Nada mais. A listagem completa fica assim: 2, 3, 5, 7, 11, 13, 17 e 19. O 2 é o único primo par, o que já elimina metade dos candidatos só com esse fato. O 1 não é primo por definição, então muitos erram aí na primeira vez. Eu já vi isso acontecer em teste de triagem pra vaga de dev júnior, pessoa marcou o 1 como primo e foi pra casa na hora. O método clássico é o crivo de Eratóstenes, e ele serve perfeitamente pro intervalo que a gente tá tratando. Você começa com uma lista de 2 até 20, marca o primeiro número da lista (que é 2) como primo e riscia todos os múltiplos dele. Depois pega o próximo não riscado (3), marca como primo e riscia os múltiplos dele. Repete até chegar na raiz quadrada do limite superior, que no caso é 4,47, então você para em 4. Os que sobrarem são os primos.

No papel leva uns dois minutos. Em código, um loop simples com a verificação módulo 2 até a raiz quadrada resolve em tempo insignificante pra esse tamanho. Pra números maiores a coisa muda de figura, claro, mas aqui é só pra entender o conceito.

Armadilhas que eu vejo todo dia

A principal é confundir primo com ímpar. Todo primo maior que 2 é ímpar, mas nem todo ímpar é primo. O 9 é ímpar, mas 9 é divisível por 3. O 15 também. O 25, fora do intervalo, mas o erro de lógica é o mesmo. Outro erro clássico: achar que 2 não é primo porque é par. É primo sim, é o único primo par que existe. Tem também a questão de otimização. Muita gente escreve um teste de primalidade que verifica divisão por todos os números de 2 até n-1. Isso funciona pro meu exemplo, mas é completamente inviável pra números grandes. A otimização real é parar em raiz quadrada e pular pares depois do 2. Isso reduz o trabalho de forma absurda.

Um caso real que eu tive

Eu precisei listar primos menores que 1000 num script de automação pra validar hashes. O código ingênuo que eu tinha inicialmente demorava cerca de 4 segundos pra rodar. Depois que eu apliquei o crivo com otimização de parar na raiz quadrada, caiu pra 0,03 segundos. Não é exagero, é exatamente essa diferença. A lição é simples: o algoritmo errado pra um problema pequeno ainda é o algoritmo errado, mesmo que o resultado final pareça o mesmo. Se você precisa só da lista pra memorizar ou pra uma tarefa escolar, decor 2, 3, 5, 7, 11, 13, 17, 19 e está pronto. Se vai implementar isso num sistema, use crivo de Eratóstenes com as otimizações que citei e não perca tempo com verificação brute force.