Lista Dos Numeros Primos

Como gerar uma lista de números primos na prática

Gerar uma lista de números primos parece simples no papel, mas a coisa desandava rápido quando você precisava ir além dos primeiros milhares. Eu já passei sufoco num projeto de criptografia antiga onde o requisito era ter todos os primos abaixo de 10 milhões para testes de segurança. A abordagem ingênua que quase todo mundo tenta primeiro — verificar cada número individualmente com divisão sucessiva — quebra miseravelmente nessa escala. Para 10 milhões de candidatos, esse método bobeiro leva horas. Eu estava há 3 horas rodando quando percebi que estava fazendo besteira. O Crivo de Eratóstenes é o caminho real. A ideia é elementar: você marca todos os múltiplos de cada primo encontrado, e o que sobrar não marcado é primo. A complexidade é O(n log log n), o que para 10 milhões significa basicamente segundos em qualquer máquina razoável. Implementação direta em Python leva uns 15 minutos de código e roda em menos de 3 segundos num notebook comum.

Construindo sua lista dos numeros primos

A versão mais pura do crivo aloca um array booleano do tamanho do limite desejado. Começa marcando 0 e 1 como não primos, depois itera de 2 até a raiz quadrada do limite. Para cada número ainda marcado como primo, marca todos os seus múltiplos a partir do seu quadrado — não precisa começar do dobro porque múltiplos menores já foram tratados por primos anteriores. Essa otimização do ponto de partida já reduz o trabalho em cerca de metade comparado à versão didática que aparece em muitos livros. O problema é que o crivo clássico gasta memória proporcional ao limite. Para 10 milhões de inteiros, um array booleano puro consome uns 10 MB, o que é tranquilo. Mas se você precisar de primos até 1 bilhão, o array único exige cerca de 1 GB de memória RAM. Aí entra o crivo segmentado, que processa o intervalo em blocos menores. Você ainda usa os primos até a raiz quadrada do limite total para fazer as marcações, mas a lista principal cabe em memória porque é tratada por segmentos. Para 1 bilhão com blocos de 1 MB, o consumo cai para algo em torno de 2-3 MB no total, e a velocidade fica numa faixa razoável — uns 10 a 15 segundos em Python, menos em C.

Uma coisa que muita gente não percebe: se o objetivo é só listar os primos sem fatorar números específicos depois, o crivo é imbatível. Mas se você precisa testar primalidade de números grandes isolados — tipo verificar se um número de 50 dígitos é primo — o crivo não serve de nada. Aí você migra para testes probabilísticos como Miller-Rabin, que são exponencialmente mais eficientes para números desse porte. Use o crivo para listas densas em intervalos pequenos. Use Miller-Rabin para primalidade de números esparsos e grandes. Misturar as duas coisas sem critério é erro comum. Também vale lembrar que existem listas prontas e confiáveis na internet. O site PrimePages (primenumbers.gov) mantém tabelas atualizadas, e o OEIS (A000040) tem a sequência completa com mais de 1,5 milhão de entradas disponíveis para download em formato de texto puro. Se você só precisa consultar e não implementar, baixar uma lista pré-computada é trivial. O problema é que arquivos enormes — acima de 100 milhões de primos — podem pesar centenas de megabytes, e processá-los em linguagens interpretadas fica lento por causa do overhead de parse. Em C ou Go, lendo diretamente do disco, o throughput é na casa dos milhões deentries por segundo.

Se sua aplicação exige distribuição uniforme de primos para gerar chaves ou hashes, prestar atenção na densidade ajuda. O teorema dos números primos diz que a quantidade de primos até N é aproximadamente N / ln(N). Isso significa que entre 1 milhão e 2 milhões há cerca de 78.000 primos, mas entre 1 bilhão e 1 bilhão e meio a queda para uns 50.000. Se você precisa de um primo randômico dentro de um intervalo grande, simplesmente testar números ímpares consecutivos a partir de um ponto aleatório encontra um primo em média a cada ln(N) tentativas. Para N = 10^9, isso dá roughly 20 testes de primalidade, o que é praticamente instantâneo com Miller-Rabin. O único ponto fraco real do crivo de Eratóstenes é a necessidade de memória contígua para a versão não segmentada. Em ambientes embarcados ou com restrições severas de RAM, essa limitação pode ser decisiva. Nesse caso, o crivo segmentado resolve, mas com um custo extra de implementação. Não é complicado, mas exige cuidado com os índices de cada segmento para não errar as marcações. Um erro de off-by-one aqui gera primos faltando na lista sem nenhum aviso — o código roda, produz resultado, e o resultado está errado. Debugar isso leva mais tempo do que implementar corretamente desde o início.

Quando não usar o crivo

Se o seu cenário envolve números maiores que 10^12, o crivo mesmo segmentado não escala bem. A memória necessária cresce linearmente com o tamanho do segmento, e o tempo de marcação dos múltiplos também. Para esses casos, testes de primalidade determinísticos como AKS (embora teórico demais na prática) ou combinações de Miller-Rabin com bases fixas para faixas conhecidas são mais adequados. O campo de criptografia RSA, por exemplo, trabalha com primos de centenas de dígitos, e ninguém usa crivo nisso — o tempo seria proibitivo. Outro detalhe prático: se você só precisa dos primeiros N primos, não do limite superior, uma do crivo chamada "sieve of Atkins" tem complexidade teórica melhor (O(n / log log n)), mas na prática raramente vence o Eratóstenes por causa das constantes maiores e da lógica mais. A diferença real de performance é marginal na maioria das implementações, e o código do Atkins é muito mais propenso a bugs. Fique com Eratóstenes a menos que tenha benchmark concreto mostrando contrário no seu ambiente.

Resumo do que funciona: Use crivo de Eratóstenes para intervalos até quelques centaines de millions. Use crivo segmentado para bilhões. Use Miller-Rabin para números isolados grandes. E verifique sempre com uma lista conhecida antes de confiar no seu código — pelo menos os primeiros 1000 primos, que você pode checar contra tabelas públicas em segundos.