17 É Um Número Primo

Como verificar se um número é primo na prática

A maioria das pessoas acha que testar primalidade é só dividir o número por tudo até ele mesmo. Isso funciona para números pequenos, como 17, mas desaba em qualquer coisa acima de 100. Eu já vi desenvolvedores escrevendo loops que vão até n-1 e se perguntando por que o código trava em produção. Para chegar a essa conclusão de forma eficiente, você precisa testar divisores apenas até a raiz quadrada do número. No caso do 17, a raiz quadrada é aproximadamente 4,12. Então você testa apenas os primos menores ou iguais a 4: 2 e 3. 17 não é divisível por 2 (é ímpar) e não é divisível por 3 (17 dividido por 3 dá 5,66...). Conclusão: 17 é primo. O teste básico que eu uso no dia a dia é esse:

Se n

= 1, não é primo. Se n == 2, é primo. Se n for par, não é primo. A partir daí, itera de 3 até sqrt(n) com incremento de 2, testando se n % i == 0. Se encontrar algum divisor, para e diz que não é primo. Se o loop terminar sem achá-lo, é primo. Achei um problema interessante trabalhando com geração de chaves RSA para um sistema interno. O código pedia para gerar dois primos grandes, e eu estava usando um teste de primalidade ingênuo que simplesmente testava todos os ímpares até o número. Em produção, com números de 512 bits, isso levava horas. Na verdade, não chegava a terminar em tempo útil. A solução foi trocar para o teste de Miller-Rabin com pelo menos 20 rodadas. Com essa mudança, o tempo caiu de horas para cerca de 40 milissegundos. Não é perfeito — existe uma probabilidade extremamente baixa de um composto passar no teste — mas na prática, para a faixa de bits que usávamos, a chance de erro era menor que 1 em 4 quatrilhões. Uma coisa que ninguém ensina direito: o teste de divisão até sqrt(n) só é viável para números pequenos, digamos até 10^12 no máximo. Acima disso, mesmo otimizado, fica lento porque o sqrt cresce junto com o número. Para criptografia moderna, números têm 2048 bits ou mais. Divisão simples não entra nem na conversa.

O teste de AKS, desenvolvido em 2002, é o primeiro algoritmo determinístico que prova primalidade em tempo polinomial. É elegante, mas na prática ninguém usa. A constant overhead é tão grande que um Miller-Rabin bem configurado responde muito mais rápido, mesmo sendo probabilístico. Eu tentei implementar o AKS uma vez num projeto acadêmico e desisti depois de uma semana. Não vale o esforço. Outro ponto que causa confusão: 1 não é primo. Já vi gente escrever código que trata 1 como primo e aí o resto do sistema quebrava de formas estranhas. O Teorema Fundamental da Aritmética — a base de tudo que depende de primos — só funciona porque 1 foi explicitamente excluído da definição. Se você incluir 1, a fatoração única deixa de ser única, porque você pode adicionar quantos 1s quiser na fatoração sem mudar o resultado. Se você precisa de uma lista de primos para um projeto pequeno, não implemente o teste do zero. Use uma peneira de Eratóstenes. Para gerar todos os primos até um milhão, ela roda em menos de 10 milissegundos na maioria das máquinas modernas. A complexidade é O(n log log n), o que é muito bom para a faixa de números que a maioria das aplicações práticas precisa.

O problema é que a peneira consome memória proporcional ao limite que você define. Se você precisar de primos acima de 10^10, a peneira tradicional não cabe na RAM. Aí você parte para uma peneira segmentada, que processa o intervalo em blocos. Isso resolve o problema de memória, mas introduz complexidade adicional no código. Depende do que você precisa. Para números únicos e grandes, eu recomendo simplesmente usar a biblioteca do sistema operacional ou uma biblioteca confiável como GMP. O GMP tem uma função mpz_probab_primp que faz Miller-Rabin otimizado em C. Chamar ela é muito mais seguro do que copiar e colar um algoritmo de internet. Eu já vi bibliotecas gratuitas com bugs sutis em testes de primalidade que deixavam compostos passarem como primos. Em criptografia, isso é catástrofe. Se o seu objetivo é só verificar se 17 é primo, ou qualquer outro número pequeno, um script de duas linhas em Python resolve. Mas entenda o que está acontecendo por trás. Primalidade parece simples até você tentar escalar.