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. 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. 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.