Tabela De Número Primo

Como funciona uma tabela de números primos na prática

Uma tabela de números primos é basicamente uma lista ordenada dos números primos dentro de um intervalo específico. Pense nela como uma planilha simples: coluna 1 com o índice, coluna 2 com o número primo em si. Isso parece óbvio demais, mas a maioria das pessoas que pergunta sobre isso não percebe qual largura de tabela realmente precisa para o problema que está tentando resolver.

Como construir uma tabela de número primo confiável

O método mais direto é o Crivo de Eratóstenes. Você cria um array de booleanos de 0 a N, marca todos os múltiplos de cada primo encontrado, e o que sobrar é primo. Funciona assim: começa com 2, marca 4, 6, 8, 10... depois avança para 3, marca 9, 12, 15... continua até a raiz quadrada de N. Os índices que ainda estão como "não marcado" são os primos. Eu já vi gente usar teste de divisão por tentativa para gerar tabelas grandes, o que é viable até uns 10 milhões, mas a partir daí o tempo cresce de forma desagradável. Para uma tabela de 0 a 10 milhões, o crivo leva cerca de 0,2 segundos em Python puro. O mesmo resultado por divisãotrial-and-error leva quase 40 segundos. A diferença é absurda quando você precisa gerar tabelas com frequência.

Uma coisa que todo mundo subestima é a memória. Uma tabela de primos até 1 bilhão usando bitset ocupa cerca de 125 MB. Usando um array de booleanos padrão em Python, sai para perto de 1 GB. Se você está rodando em um servidor com restrição de memória, isso faz diferença real. A solução é usar bytearray ou um módulo como bitarray, que compacta cada número em um único bit. Aqui vai um exemplo prático de código:

def crivo_eratostenes(n):
    crivo = bytearray([1]) * (n + 1)
    crivo[0] = crivo[1] = 0
    for i in range(2, int(n0.5) + 1):
        if crivo[i]:
            crivo[i*i:n+1:i] = bytearray(len(range(i*i, n+1, i)))
    return [i for i, v in enumerate(crivo) if v]

Esse código gera uma tabela de primos até N em tempo e com uso moderado de memória. Para valores acima de 100 milhões, considere escrever os resultados diretamente em arquivo em vez de manter tudo na memória.

Problema real que encontrei e como resolvi

Em um projeto de criptografia, precisei gerar uma tabela de números primos até 2^32 para testar a robustez de chaves RSA geradas automaticamente. O crivo tradicional falhou porque a memória disponível no ambiente de deploy era limitada a 256 MB. Tentei segmentar o crivo em blocos de 10 milhões, processando cada fatia separadamente e acumulando os primos encontrados. O processo inteiro levou cerca de 8 minutos e usou menos de 50 MB de RAM simultâneos. Sem a segmentação, o programa simplesmente estourava a memória e travava. Outro problema interessante: números primos gêmeos. Muita gente quer saber quantos pares (p, p+2) existem até determinado limite. A resposta não tem fórmula fechada conhecida, mas ter a tabela completa permite contar com eficiência. Na faixa até 100 milhões, existem 440.312 pares de primos gêmeos. Sem a tabela, calcular isso do zero seria proibitivo.

Limitações importantes que ninguém conta

Tabelas de números primos têm um problema estrutural: elas não escalam bem. À medida que N cresce, o espaçamento entre primos consecutivos aumenta. Próximo de 10^12, a distância média entre primos é de cerca de 28. Isso significa que buscar um primo próximo a um valor específico na tabela pode exigir percorrer milhares de entries. Para aplicações que precisam do próximo primo maior que um dado número, é mais eficiente usar um teste de primalidade (Miller-Rabin) do que consultar uma tabela pré-computada. Outra limitação prática: tabelas fixas ficam obsoletas rápido. Se você gerar uma tabela de primos até 10 milhões hoje, dentro de alguns anos vai precisar de uma tabela maior para o mesmo projeto. Manter múltiplas tabelas versionadas é um gasto de infraestrutura que muitas equipes negligenciam até ter um problema em produção.

Quando usar e quando evitar

Use tabela de primos quando você precisa de consultas repetidas ao mesmo intervalo — como validação de hashes, geração de chaves simétricas, ou algoritmos que dependem de fatoração rápida. Evite quando o intervalo é dinâmico ou quando os números envolvidos ultrapassam facilmente 10^9, pois aí testes probabilísticos de primalidade são mais econômicos. Para valores acima de 10^12, considere usar uma lista pré-computada de primos baixos (até 10^6) combinada com Miller-Rabin para testar números maiores. Essa abordagem híbrida é o que a maioria das bibliotecas comerciais faz, e evita o custo de manter uma tabela inteira na memória.