Qual Dos Números A Seguir É Primo

Uma explicação honesta sobre como identificar números primos

Você já se deparou com aquela questão de prova ou concurso que pede para determinar qual dos números a seguir é primo e trava na hora? A maioria das pessoas tenta dividir por tudo que é número e perde tempo. Eu já vi gente passando mais de dez minutos num só número quando o teste é bem mais rápido do que parece. Um número primo é simplesmente aquele que só é divisível por 1 e por ele mesmo. Ponto. Não tem mistério na definição, mas o problema aparece na hora de aplicar isso na prática, principalmente com números grandes. O método básico é tentar dividir o número por todos os primos menores ou iguais à sua raiz quadrada. Se nenhuma dessas divisões resultar em resto zero, o número é primo. Parece trivial, mas muita gente erra no passo mais importante: parar de testar na raiz quadrada e continuar tentando dividir por números aleatórios.

Deixe eu dar um exemplo concreto. Digamos que você tenha a sequência 15, 21, 29, 33, 37 e precise achar o primo. Vamos testar cada um. 15 é divisível por 3 e por 5. Sai fora. 21 é divisível por 3 e por 7. Também não é. 29 — aqui é onde as pessoas costumam vacilar. A raiz quadrada de 29 é aproximadamente 5,38. Então só preciso testar os primos até 5: 2, 3 e 5. 29 não é par, então não divide por 2. A soma dos dígitos é 11, que não é divisível por 3, então 29 não divide por 3. Não termina em 0 ou 5, então não divide por 5. Cheguei até o limite da raiz quadrada e nenhuma divisão funcionou. 29 é primo. 33 divide por 3. 37 também exige o mesmo teste. Raiz quadrada de 37 é cerca de 6,08. Testamos 2, 3 e 5. Não é par. Soma dos dígitos é 10, não divisível por 3. Não termina em 0 ou 5. 37 é primo também. Nesse exemplo, teríamos dois primos: 29 e 37.

Agora vou te contar algo que aprendi na marra. Trabalhando com análise de dados, precisei validar um conjunto de números para um algoritmo de criptografia simples. Tinha uma lista com milhares de candidatos e o script estava retornando falsos positivos. Descobri que o problema era um número que parecia primo: 561. Ele passou em todos os testes primários porque não é divisível por nenhum primo pequeno. 561 dividido por 2 dá resto. Por 3 a soma dos dígitos é 12, então na verdade ele divide por 3, mas o teste inicial tinha um bug que ignorava esse critério. Quando corrigi, achei que estava pronto. Errado. 561 é um exemplo clássico de número de Carmichael — ele passa no teste de primalidade de Fermat para várias bases mesmo sendo composto. 561 = 3 × 11 × 17. A lição que levei pra vida foi: o teste de divisibilidade por 2, 3 e 5 é rápido, mas para números maiores você precisa de métodos mais robustos, como o teste de Miller-Rabin ou a criva de Eratóstenes quando for listar vários números de uma vez. Outro detalhe que pouca gente menciona: o número 2 é o único primo par. Todo o resto dos primos é ímpar. Se alguém te perguntar qual dos números a seguir é primo e houver um 2 na lista, essa é muitas vezes a resposta mais rápida, porque elimina a necessidade de qualquer cálculo. Basta verificar se os outros números são pares ou múltiplos óbvios. Também vale saber que 1 não é primo. Isso parece bobo, mas é um erro brutal que aparece em questões de múltipla escolha com frequência. Os criadores de prova colocam 1 como distrator justamente porque quem decorou o começo da lista de primos (2, 3, 5, 7...) pode marcar sem pensar.

Uma dica prática que economiza tempo: memorize os primeiros 25 primos. 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97. Com isso, a maioria das questões do dia a dia fica resolvida de cabeça. Para números acima de 100, aí sim você recorre à divisão pela raiz quadrada. Se o seu objetivo é verificar primalidade de forma programática, a abordagem mais eficiente para listas pequenas é a criva de Eratóstenes. Para números únicos muito grandes, o teste de Miller-Rabin com várias rodadas é o padrão da indústria. Nenhum deles é perfeito — a criva consome memória proporcional ao número que você quer analisar, e Miller-Rabin é probabilístico, o que significa que existe uma chance infinitesimal de erro que diminui com cada rodada adicional. Para a grande maioria das situações práticas, essas limitações são irrelevantes. O que eu mais vejo as pessoas fazendo errado é confundir número ímpar com número primo. Quase todo ímpar é primo pra quem não prestou atenção. 9, 15, 21, 25, 27, 33, 35 — todos ímpares, nenhum primo exceto alguns. A regra de Ouro aqui é: se o número não é 2, teste a divisibilidade por 3 usando a soma dos dígitos antes de qualquer outra coisa. É o filtro que elimina a maior parte dos candidatos compostos com o menor esforço.