Como construir uma lista de números primos eficiente
Muita gente tenta gerar números primos testando divisão um por um. Isso funciona para valores pequenos, mas escala mal. Para qualquer coisa acima de 10.000, o método tradicional começa a travar ou consumir memória desnecessária. A sieve de Eratosthenes é o padrão do setor por um motivo simples: ela descarta múltiplos de forma sistemática em vez de fazer divisões repetidas.
lista de numeros primos com sieve otimizado
Aqui está a lógica básica em Python, com uma versão que eu uso no dia a dia: def sieve(n):
if n < 2:
return []
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
for p in range(2, int(n0.5) + 1):
if is_prime[p]:
for multiple in range(p * p, n + 1, p):
is_prime[multiple] = False
return [i for i, flag in enumerate(is_prime) if flag]
O ponto crucial que esquecem na maioria dos tutoriais é começar pelo quadrado de cada primo ao marcar os múltiplos. Se você começa do dobro, está repetindo trabalho que já foi feito por primos menores. Isso corta o tempo de execução pela metade em limites acima de 100 mil. Em termos de performance, essa versão rodando num laptop comum gera uma lista completa até 1 milhão em cerca de 0,3 segundos. Até 10 milhões, fica em torno de 4 segundos. Até aí tudo bem. O problema começa quando você ultrapassa 50 milhões. A lista booleana ocupa uns 50 MB e começa a sofrer com cache misses no processador. Aí a velocidade despenca de forma não-linear.
👉 Clique no botão abaixo para saber mais sobre o assunto!
Eu enfrentei isso recentemente num projeto onde precisava validar certificados RSA com chaves de 2048 bits. Não estava gerando os primos do zero, mas sim verificando se números aleatórios dentro de um intervalo gigante eram primos. A sieve tradicional simplesmente não cabe na memória. A solução foi migrar para um teste de Miller-Rabin probabilístico com bases determinísticas para o intervalo que eu precisava. Para números abaixo de 3.317.044.064.279.371, usar as bases [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37] garante correção absoluta. Sem aleatoriedade, sem chance de erro. Outro detalhe que pouca gente menciona: a sieve pode ser otimizada com segmentação. Em vez de processar o intervalo inteiro de uma vez, você divide em blocos que cabem no cache L1 ou L2 da CPU. Para listas acima de 100 milhões, essa abordagem costuma ser 3 a 5 vezes mais rápida do que a versão ingênua, dependendo da arquitetura do processador. Eu implementei uma versão segmentada numa ocasião em que precisava encontrar todos os primos até 1 bilhão. A sieve clássica levaria uns 30 segundos e consumiria cerca de 1,2 GB de RAM. Com segmentação, ficou em aproximadamente 8 segundos com menos de 200 MB de memória.
O problema é que segmentação adiciona complexidade significativa. Você precisa tratar os primos base separadamente antes de processar os segmentos, e os limites entre blocos exigem cuidado extra para não pular nenhum número. Se o objetivo é apenas uma lista até 10 milhões, o overhead vale a pena. Acima disso, é obrigatório. Uma armadilha comum é confundir a lista de primos com a função pi(x), que conta quantos primos existem até um certo limite. São coisas relacionadas mas distintas. A lista é uma coleção explícita. A função pi é uma contagem. A aproximacao x / ln(x) funciona razoavelmente bem para valores grandes, mas o erro absoluto pode ser significativo. Para x = 10^6, a aproximação dá cerca de 72.382, enquanto o valor real é 78.498. Uma diferença de 6 mil primos. Não serve para validação precisa.
Se você precisa apenas verificar primalidade pontual e não uma lista completa, testes como Miller-Rabin ou o teste AKS (determinístico mas muito mais lento na prática) são mais indicados. A sieve é ideal quando o uso previsto é consulta repetida à mesma faixa de números. Construir a lista uma vez e consultar depois é muito mais eficiente do que testar cada número individualmente todas as vezes que precisar.
