Lista De Números Primos

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

Muita gente começa tentando dividir cada número por todos os anteriores para ver se é primo. Isso funciona para números pequenos, mas desaparece rapidamente quando você precisa de algo além de 1.000. Eu passei um tempo nesse caminho antes de aprender que o crivo de Eratóstenes é basicamente obrigatório para qualquer coisa além de curiosidade acadêmica. O crivo funciona criando um array de booleanos, marcando como não-primo todos os múltiplos de cada número encontrado, começando do 2. A complexidade é O(n log log n), o que significa que gerar uma lista de milhões de primos leva segundos em vez de horas. Para uma lista de números primos até 1 milhão, isso reduz o tempo de processamento de algo como 45 minutos para cerca de 2 segundos num processador comum.

Lista de números primos: limites e casos que quebram o código

O problema que eu encontrei na prática foi mais chato do que deveria. Eu estava implementando o crivo para um sistema que precisava de primos até 10 bilhões. O array booleano original preenchia toda a memória disponível. A solução foi implementar o crivo segmentado, que processa o intervalo em pedaços menores, mantendo na memória apenas os primos até a raiz quadrada do limite superior — no caso de 10 bilhões, apenas os primos até cerca de 100 mil. Isso reduziu o uso de memória de alguns gigabytes para menos de 5 megabytes. A outra armadilha que as pessoas frequentemente encontram é confundir velocidade bruta com eficiência. Você pode otimizadar o crivo inicial marcando apenas os ímpares desde o começo, cortando o tamanho do array pela metade e acelerando o processo em aproximadamente 40%. Usar um bytearray em vez de uma lista de booleanos em Python também ajuda bastante, já que ocupa um byte por entrada em vez de vários bytes por objeto booleano.

Quais primos realmente importam em sistemas reais

Em criptografia RSA, por exemplo, você não usa uma lista pré-computada de primos. Você gera primos grandes aleatoriamente e testa com probabilidades. Mas para hash tables, geração de chaves menores e algoritmos de numeração, ter uma lista pré-calculada faz sentido. O tamanho ideal depende completamente do seu caso de uso. Para a maioria das aplicações de infraestrutura e serviços internos, uma lista até 10 milhões cobre quase todas as necessidades práticas. Se você está trabalhando com números maiores do que isso, convém usar um gerador sob demanda em vez de armazenar tudo na memória. Um gerador que usa o crivo segmentado produz primos conforme solicitado, sem precisar calcular tudo de uma vez. Em Python, uma função com yield que rastreia múltiplos usando um dicionário de compositeiros atinge boas velocidades e memória constante, embora seja mais lenta do que o crivo completo para grandes ranges porque não aproveita a localidade de cache da mesma forma.

Implementação prática com detalhes que fazem diferença

Aqui está uma versão robusta do crivo de Eratóstenes em Python que lida com ranges grandes sem problema: def sieve(limit):
if limit < 2:
return []
is_prime = bytearray(b'\x01') * (limit + 1)
is_prime[0:2] = b'\x00\x00'
for i in range(2, int(limit0.5) + 1):
if is_prime[i]:
is_prime[i*i : limit+1 : i] = b'\x00' * len(range(i*i, limit+1, i))
return [i for i, p in enumerate(is_prime) if p]

O truque aqui é a fatia com step. Em vez de um loop aninhado que marca múltiplo por múltiplo, a atribuição de fatia faz todo o trabalho em C, o que é dramaticamente mais rápido. Para um limite de 100 milhões, isso roda em torno de 3 segundos no meu machine. Se você precisar de algo ainda mais rápido e não se importa com dependências externas, bibliotecas como primePy ou o módulo integrado do sympy oferecem funções de listas de primos altamente otimizadas. O sympy, por exemplo, usa uma versão ainda mais refinada do crivo que inclui otimizações de wheel factorization, pulando múltiplos de 2, 3 e 5 simultaneamente. Isso pode dar mais um ganho de 20 a 30% comparado ao crivo básico.

O que observar antes de colocar em produção

Um detalhe que pega muita gente desprevenida: o crivo clássica consome memória proporcional ao limite superior. Lista de números primos até 100 milhões gasta cerca de 100 megabytes com bytearray. Até 1 bilhão, cerca de 1 gigabyte. Se seu serviço roda com memória limitada, essa abordagem simplesmente não escala. Nesse caso, volte ao gerador com crivo segmentado, mesmo que mais lento, ou limite o range máximo que você pede. Também é útil saber que números primos acima de 1 milhão têm espaçamento crescente entre eles. A média entre primos consecutivos perto de 1 milhão é de cerca de 14. Isso não afeta o crivo diretamente, mas é relevante se você estiver usando primos para hashing ou tabelas de dispersão, pois buckets baseados em primos próximos tendem a ter distribuição mais uniforme do que potências de 2.

Não existe uma tabela universal de primos que resolva tudo. Escolha a abordagem baseada no tamanho do range que você precisa, na memória disponível e se precisa de todos os primos de uma vez ou pode gerar sob demanda. O crivo com bytearray é o ponto de partida razoável para a maioria dos casos. Quando ele falha, o crivo segmentado ou uma biblioteca especializada é o próximo passo.