Como gerar uma lista de números primos de forma prática
A maioria das pessoas tenta testar cada número individualmente para ver se é primo. Isso funciona para os primeiros 100, mas vira uma perda de tempo séria quando você precisa de uma lista mais longa. O método que eu uso na prática é o Crivo de Eratóstenes. É simples, rápido, e não exige fórmula mágica. A ideia básica é essa: você escreve todos os números de 2 até N, marca o 2 como primo e riscia todos os múltiplos dele. Depois avança para o próximo número não riscado, que é o 3, e risca todos os múltiplos de 3. Repete até chegar em sqrt(N). O que sobrar são os primos.
O que esperar de uma lista numeros primos bem feita
Uma lista bem construída de números primos segue uma propriedade conhecida mas pouco útil na prática: a distribuição deles fica cada vez mais esparsa conforme os números crescem. Entre 1 e 100, você tem 25 primos. Entre 1.000 e 1.100, são 15. Entre 1.000.000 e 1.010.000, são apenas 66. Isso é o Teorema dos Números Primos, e significa que quanto mais alto você vai, mais espaço vazio aparece na lista. Outra coisa que poucos lembram: depois do 2 e do 3, todo número primo é da forma 6k ± 1. Isso não é só curiosidade. Usar esse filtro antes de rodar o crivo reduz o trabalho inicial em cerca de dois terços, porque você já elimina todos os múltiplos de 2 e 3 sem precisar processá-los.
Vou dar um exemplo rápido. Suponha que você quer todos os primos até 30. O crivo funciona assim: começa com [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30]. Marca 2 como primo, risca 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30. Próximo não riscado é 3, risca 9, 15, 21, 27. Próximo é 5, mas 5² = 25 que já foi riscado. Para. O resultado é [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]. Na prática, eu implemento isso em Python com um array booleano. Para listas até 10 milhões, o crivo clássico roda em menos de 2 segundos em uma máquina comum. Memória necessária é aproximadamente N bits, ou seja, cerca de 1,2 MB para 10 milhões de números. Tudo viável.
O problema que eu encontrei na prática
Uma vez precisei gerar uma lista numeros primos até 100 milhões para um projeto de criptografia caseira. O Crivo de Eratóstenes padrão funcionou, mas o consumo de memória disparou para cerca de 12 MB com o array booleano. Em ambientes com restrição severa, isso é um problema. A solução que eu adotei foi o crivo segmentado: processa o número em blocos de, digamos, 10 milhões, reutilizando o mesmo bloco de memória. Assim, a lista até 100 milhões cabe em cerca de 1,5 MB de RAM, mas leva aproximadamente 10 vezes mais tempo para completar. Compromisso direto entre velocidade e memória.
👉 Clique no botão abaixo para saber mais sobre o assunto!
Pegadinhas comuns ao gerar listas de primos
O erro mais frequente é parar o crivo em N/2 em vez de sqrt(N). Você pode pensar que precisa testar divisores até a metade, mas não precisa. Se um número tem um fator maior que sua raiz quadrada, o parceiro desse fator já foi encontrado antes. Parar em sqrt(N) corta o trabalho pela metade em média e é matematicamente correto. Outro erro comum é tratar o 1 como primo. Ele não é. O próprio conceito de primalidade exige exatamente dois divisores positivos, e o 1 tem apenas um. Se você incluir o 1 na lista, qualquer algoritmo que dependa dela — teste de primalidade, fatoração, geração de chaves — vai retornar resultados errados silenciosamente.
Se você está gerando a lista para uso em produção, vale considerar algo que a maioria ignora: a velocidade de escrita no disco pode ser o gargalo, não o cálculo em si. Escrever uma lista de 576 mil primos até 10 milhões em um arquivo texto simples leva mais tempo do que calcular o crivo em hardware modesto. Use binário se o consumo de espaço importar, ou compacte com gzip se a lista precisa ser distribuída. Para listas muito grandes, além do crivo segmentado, existe o crivo de Atkin, que é teoricamente mais rápido com complexidade O(N / log log N). Na prática, a constante multiplicadora é maior e ele só compensa acima de alguns bilhões. Para a maioria dos casos reais, o Eratóstenes continua sendo a escolha certa.
Se quiser testar agora mesmo, uma implementação mínima em Python cabe em 15 linhas e gera os primos até 1 milhão em cerca de 0,8 segundo no meu computador. O crivo segmentado para 100 milhões exige cerca de 18 segundos e 1,5 MB de RAM. A diferença é real e mensurável, não teórica. Para quem precisa apenas consultar uma lista pronta, existem repositórios com os primeiros milhões de primos em formato CSV. O risco é que dados prontos nem sempre são validados. Sempre faça uma verificação rápida: confira se o 1000º primo é 7919. Se não for, a fonte está errada e você vai herdar o erro cegamente.
O que falta nesses guias é um aviso sobre limites. Crivo de Eratóstenes clássico quebra em listas acima de 2 bilhões porque o array booleano exige RAM excessiva. Crivo segmentado contorna isso, mas a complexidade de implementação sobe. Se o objetivo é apenas testar se um número isolado é primo, o teste de Miller-Rabin é mais eficiente e usa uma fração da memória. Cada ferramenta serve a um cenário diferente, e confundir os dois é comum.
