Números Par E Primo Ao Mesmo Tempo

A primeira verificação é o 2. Se entrar nele, retorna True na hora. A segunda linha descarta qualquer coisa menor ou igual a 2 e qualquer par acima de 2. A partir daí o laço só testa divisores ímpares, pulando de 2 em 2, até a raiz quadrada do número. Isso reduz drasticamente o número de iterações comparado a testar todos os números até n-1. Num sistema de geração de chaves assimétricas que eu mantive por dois anos, o módulo de criptografia chamava uma função de triagem de primos antes de iniciar o teste de Miller-Rabin. A função de triagem tinha um fallback que, se o número passado fosse par e maior que 2, simplesmente descartava. O problema era que o gerador aleatório podia, em raras ocasiões, produzir exatamente o número 2 como candidato. Como a lógica do sistema assumia implicitamente que primos grandes seriam gerados, o 2 escapava da proteção e o algoritmo principal entrava num loop de otimização que não previa esse caso. O resultado era um timeout silencioso que só aparecia em testes de integração sob carga, quando a probabilidade de colisão aumentava. A correção foi adicionar um check explícito no início de todo pipeline de geração: se o candidato for 2, trata como caso especial e pula direto pra validação. Sem isso, o sistema simplesmente travava em intervalos imprevisíveis. Eu levei umas três semanas pra rastrear até a raiz porque o log não mostrava erro nenhum, só timeouts genéricos.

O que programadores juniores sempre erram

Erros comuns que eu vejo repetidamente: Colocar o check de paridade depois do laço de teste de primalidade. Funciona, mas é ineficiente. Se o número for par e grande, você já perdeu tempo rodando o laço inteiro pra descobrir que não é primo. Sempre filtre pares antes. Usar a condição n % 2 != 0 como critério de primo. Um número ímpar não é automaticamente primo. 9, 15, 21, 25... a lista é enorme. Ímpar é condição necessária mas não suficiente.

Testar divisibilidade até n em vez de até a raiz quadrada. Para números grandes isso transforma um algoritmo que rodaria em milissegundos num que leva minutos ou horas. A diferença não é linear, é radical.

Limitações reais que ninguém avisa

O teste que mostrei funciona bem para números até algumas centenas de bilhões no Python comum. Acima disso a coisa muda de figura. Para números com mais de 30 dígitos, esse algoritmo simplesmente não cabe mais na janela de tempo aceitável. Você precisa migrar pra Miller-Rabin com bases determinísticas ou pra testes de primalidade probabilísticos com múltiplas rodadas. Outro ponto: em criptografia real, você nunca quer o menor primo possível. O 2 é matematicamente válido mas cryptographicamente inútil sozinho. Chaves RSA começam com primos de pelo menos 512 bits cada. Gerar esses primos exige técnicas específicas de amostragem que não são triviais. Só saber que 2 é par e primo não te ajuda em nada nesse cenário.

Alternativas quando o método simples não serve

Se você precisa de primos grandes em produção, abandone o teste por divisão. Use a biblioteca gmpy2 se estiver em Python, ou a função mpzprobabprime_p do GMP diretamente. Elas implementam Miller-Rabin otimizado em C e rodam ordens de grandeza mais rápido que qualquer coisa que você escreva em linguagem interpretada. Para geração de primos grandes com garantia determinística, o algoritmo de AKS existe mas é mais teórico que prático. Ninguém usa em produção. O caminho padrão é gerar um candidato aleatório ímpar, aplicar Miller-Rabin com bases fixas conhecidas como seguras para o tamanho desejado, e pronto. Isso cobre a vasta maioria dos casos reais. Voltemdo ao ponto original: existem infinitos números pares. Existem infinitos números primos. A interseção desses dois conjuntos tem exatamente um elemento. Saber disso é fácil. Saber o que fazer com essa informação quando ela aparece num sistema real é o que separa quem apenas decorou definição de quem resolve problema de verdade.