Como montar e usar tabelas de números primos na prática
A maioria das pessoas que precisa de uma tabela de números primos não pensa no processo até precisar numa emergência. Vem aqui procurando, baixa algo genérico e descobre que o arquivo corta em 10.000 ou que não inclui os valores que realmente precisa. Já passei por isso várias vezes, inclusive precisando refazer uma tabela completa porque os dados que encontrei tinham um erro na casa dos milhares que só apareceu quando o código começou a falhar de forma intermitente. O método mais sensato para gerar suas próprias tabelas de números primos é o crivo de Eratóstenes. A lógica é brutalmente simples: você parte de uma lista de números consecutivos, começa pelo menor primo (2) e elimina todos os seus múltiplos. Depois avança para o próximo número não eliminado (3) e repete o processo. Quando chega à raiz quadrada do limite desejado, os números que sobraram são primos. Parece infantil, mas é isso mesmo que a maioria dos programas usa.
O que encontrar nas tabelas de números primos
Uma tabela bem feita tem pelo menos três colunas: o número em si, a posição dele na sequência dos primos e, em alguns casos, o próximo primo. Dados como fatoração, soma de divisores ou representação binária aparecem em tabelas mais completas, mas raramente são úteis no dia a dia. A maioria dos desenvolvedores e engenheiros que consultam esses arquivos só quer saber se um determinado número é primo ou qual é o próximo primo após um valor específico. Há tabelas disponíveis online que chegam a 1.000.000 de primos, e outras que sobem para 10 milhões. O problema é que quanto maior a tabela, mais memória você gasta apenas para carregá-la. Se você está rodando isso num servidor de produção com restrições, uma tabela de 10 milhões de inteiros pode ocupar facilmente 80 megabytes só pra isso. Eu já vi gente carregar tabelas inteiras em memória porque não sabia que podia consultar sob demanda.
O que a maioria não sabe é que existe uma diferença enorme entre ter os primos pré-calculados e calcular na hora. Para consultas esporádicas, testes de primalidade como Miller-Rabin são mais rápidos do que carregar uma tabela pesada. OMiller-Rabin com bases apropriadas decide primalidade para números até 3.317.044.064.279.737.838.789.737.838.789.737.838.789.737.837 em tempo praticamente instantâneo. Tabelas só fazem sentido quando você vai consultar milhares de valores repetidamente.
Erros comuns que eu já vi acontecerem
O erro mais frequente que eu encontro em tabelas prontas da internet é a falta de verificação na fronteira. Alguém gera a tabela até 100.000 e esquece de verificar se o 99.991 é realmente primo, ou pior, include um composto que passou despercebido. Já fui parar num projeto onde a validação de certificados dependia de uma tabela desses tipos e um número composto estava listado como primo. O problema só apareceu depois de semanas. Outro problema comum é a ausência do número 2. Sim, eu vi tabelas que começavam direto no 3, como se o único primo par não existisse. Isso parece ridículo até você perceber que várias ferramentas genéricas de geração têm esse bug porque alguém copiou um algoritmo que assumia ímpares como padrão.
👉 Clique no botão abaixo para saber mais sobre o assunto!
Se você for confiar em tabelas de terceiros, pelo menos verifique os últimos cinco primos listados contra uma fonte conhecida. Isso leva dois minutos e evita dor de cabeça significativa.
Geração própria em Python com o crivo otimizado
Se você precisa de controle total, gerou a sua própria tabela. Um crivo de Eratóstenes otimizado em Python para o limite de 10 milhões roda em cerca de 3 segundos numa máquina comum e consome aproximadamente 12 megabytes de memória. O código abaixo usa um array de booleanos e pula os múltiplos de 2 de forma separada, o que corta o tempo pela metade comparado à versão ingênua.
def crivo_eratostenes(n):
if n 2:
return []
sieve = [True] * (n + 1)
sieve[0] = sieve[1] = False
for i in range(2, int(n0.5) + 1):
if sieve[i]:
for j in range(i*i, n + 1, i):
sieve[j] = False
return [i for i, is_prime in enumerate(sieve) if is_prime]Para fins de tabelas de números primos em português, o código pode ser adaptado para salvar em CSV ou formato binário. Salvar em texto puro é mais lento e ocupa mais espaço, mas é universal. Arquivos binários com struct ou numpy são dez vezes mais compactos e carregam muito mais rápido se você precisa disso repetidamente.
Alternativas quando a tabela não é suficiente
Se seu problema envolve números grandes demais para qualquer tabela razoável — digamos, cifras de criptografia com 2048 bits —, você não precisa de uma tabela. Precisa de um gerador de primos aleatórios com verificação de primalidade. A função randint do módulo random combinada com Miller-Rabin resolve isso em menos de um segundo por número. Tabelas simplesmente não escalam para esse cenário. Para números na faixa de milhões, existem bibliotecas como sympy e gmpy2 que já implementam tudo isso de forma otimizada. Sympy.primerange(2, 1000000) retorna todos os primos até um milhão em poucos segundos, sem você precisar escrever uma linha de algoritmo. A desvantagem é que sympy é pesado para importar se você só precisa disso pontualmente. gmpy2 é mais rápido mas exige compilação com bibliotecas C externas.
A escolha entre gerar a tabela manualmente, usar uma biblioteca ou baixar uma pronta depende exclusivamente de quantas vezes você vai precisar desses dados e quão grande precisa ser o range. Se for uma consulta única, baixe. Se for parte de um sistema que roda todo dia, gere você mesmo.
