O que são números primos na prática
Um número primo é inteiro, maior que 1, e só divisível por 1 e por ele mesmo. O 2 é primo. O 3 também. O 4 não é, porque dá para dividir por 2. O 5 é. O 6 não. Isso é a base, mas a parte que as pessoas costumam ignorar é como verificar isso no mundo real. Quando eu comecei a mexer com algoritmos de fatoração, passava horas testando primos manualmente. A primeira coisa que aprendi foi: você não precisa testar divisores acima da raiz quadrada do número. Se n = a × b e a b, então a n. Isso corta o trabalho de forma brutal em números grandes.
quais numeros sao primos e como descobrir rapidamente
Para achá-los, o método mais direto é a crivo de Eratóstenes. Você escreve os números de 2 até N, marca os primos e vai eliminando os múltiplos. Começa pelo 2, marca todos os pares maiores que 2. Vai pro 3, marca os múltiplos dele. Depois o 5, depois o 7. Quando chegar em N, o que sobrou são os primos. Em termos de performance, para uma lista até 1 milhão, esse crivo leva alguns milissegundos em qualquer linguagem razoável. Testar cada número individualmente com divisões até a raiz quadrada, um por um, é significativamente mais lento, especialmente quando a lista cresce.
Um detalhe que muita gente perde: todos os primos maiores que 3 são da forma 6k ± 1. Ou seja, depois de verificar 2 e 3, você pode pular todos os números que são divisíveis por 2 ou 3. Em vez de testar cada ímpar, testa só 6k-1 e 6k+1. Isso reduz o número de divisões em dois terços. Parece pouco, mas faz diferença quando você está rodando milhões de verificações. Aqui vai um problema real que eu tive. Estava implementando um gerador de chaves RSA pequeno para um projeto interno. O código precisava encontrar primos grandes, na casa dos 512 bits. Usar o crivo direto era inviável — você não consegue alocar um array booleano de tamanho 2^512. A solução foi usar testes probabilísticos, especificamente o teste de Miller-Rabin. Ele não prova que um número é primo de forma absoluta, mas a probabilidade de erro é tão pequena que na prática funciona. Com pelo menos 20 rodadas e bases well-chosen, a chance de um composto passar é menor que 4^(-20), algo em torno de 1 em 10^12. Para geração de chaves, isso é mais que suficiente.
👉 Clique no botão abaixo para saber mais sobre o assunto!
O que o Miller-Rabin faz, resumindo: escolhe uma base a aleatória, calcula a^(n-1) mod n, e vê se o resultado é 1. Se não for, n é composto. Se for, n é provavelmente primo. Repete várias vezes com bases diferentes e a confiança aumenta. É rápido porque usa exponenciação modular eficiente, que roda em tempo log(n). Pitfalls comuns que eu vejo todo mundo cometendo:
Primeiro, achar que testar divisibilidade até n/2 é suficiente. Não é. Até n já é o limite correto. Testar até a metade é trabalho desnecessário duplicado. Segundo, esquecer que o 1 não é primo. Esse erro aparece o tempo todo em código. Todo iniciante coloca 1 como primo e depois gasta horas debugando porque a fatoração devolve resultados errados.
Terceiro, confundir número primo com número ímpar. 9 é ímpar mas não é primo. 2 é primo e é par. Os dois conceitos não têm relação direta além do 2 ser o único primo par. Se você precisa apenas listar primos pequenos, digamos até 10 milhões, o crivo de Eratóstenes é a melhor escolha. Simples, rápido, previsível. Se precisa verificar se um número grande é primo, vá de Miller-Rabin com pelo menos 10-20 iterações. Se precisar de garantia absoluta em vez de probabilidade, existe o teste AKS, que é determinístico e polinomial, mas na prática é muito mais lento que Miller-Rabin para a maioria dos casos reais. Ninguém usa AKS em produção fora de contextos acadêmicos.
Uma lista curta dos primeiros primos serve de referência rápida: 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. A partir daí, a densidade vai caindo. Entre 1 e 100 tem 25 primos. Entre 10 mil e 11 mil, tem 106. A distribuição é caótica o suficiente pra dificultar previsão, mas regular o bastante pra teoria dos números funcionar.
