Todo Numero Primo É Impar

A verdade sobre números primos e pares que ninguém conta

Vim um cara na semana passada reclamando que o algoritmo de criptografia dele travava porque ele tinha assumido que todo primo era ímpar. Claro, o problema era simples demais — ele esqueceu do 2. Eu passei uns três anos debuggando isso em projeto de quem queria gerar chaves RSA manualmente, e a dor de cabeça foi grande até eu perceber. O todo numero primo é impar é uma ideia que parece lógica até você testar com um exemplo. A maioria das pessoas aprende primos ainda no ensino fundamental e sai com a impressão de que todos os primos são ímpares. Não é bem assim.

todo numero primo é impar: por que a afirmação está errada

Número primo é aquele que só é divisível por 1 e por ele mesmo. O 2 se encaixa nessa definição perfeitamente. Ele é par e é primo. A partir daí, todos os outros primos conhecidos são realmente ímpares — 3, 5, 7, 11, 13, 17, 19, 23... Mas o 2 continua sendo o único caso especial. Se você está testando se um número é primo e começa a dividir por 2, 3, 5, 7, pode acabar achando que o 2 não é primo porque ele é par. O workaround que eu uso hoje é simples: tratar o 2 como caso base, retornar verdadeiro imediatamente, e só então testar divisibilidade por ímpares a partir do 3. Outra pegadinha que me custo caro quando eu era iniciante: o 9. Parece primo pra quem tá aprendendo, mas 9 = 3 × 3. Eu já deixei esse bicho passar em teste unitário por causa de um erro de digitação no laço de divisão. O aprendizado foi que todo primo maior que 2 é ímpar, mas nem todo ímpar é primo.

Se o seu objetivo é verificar primalidade de forma eficiente, o teste por tentativa de divisão até a raiz quadrada do número funciona bem para valores menores que 1 milhão. Para números maiores, aí entra Miller-Rabin ou testes mais robustos. Mas pra maioria dos casos do dia a dia, testar divisibilidade por 2 primeiro e depois pelos ímpares até sqrt(n) resolve.