Como funciona uma tabela de números primos na prática
A maioria das pessoas procura uma tabela de número primo para consultas rápidas ou para validar resultados em exercícios escolares. O problema é que esses recursos da internet geralmente param nos 1.000 primeiros primos e já ficam desatualizados. Se você precisa ir além disso, não adianta só copiar e colar — precisa entender como construir a sua própria lista de forma confiável. O método mais comum é o Crivo de Eratóstenes. Você cria um array de booleanos de 0 a N, marca 0 e 1 como não primos, depois para cada número a partir de 2 até a raiz quadrada de N, elimina todos os múltiplos daquele número. Restam apenas os primos. Parece simples porque é simples, mas a implementação tem armadilhas que todo mundo cometida pelo menos uma vez.
Eu já perdi algumas horas tentando gerar uma tabela até 10 milhões usando uma abordagem ingênua de divisões sucessivas em Python. O script rodava há 47 minutos sem terminar. Troquei para o crivo com otimização de apenas números ímpares e o tempo caiu para cerca de 8 segundos. A diferença é brutal e não é algo que aparece nos tutoriais básicos.
tabela de número primo: limites e o que fazer quando eles estouram
Uma coisa que poucos explicam é que a memória necessária para o crivo cresce linearmente com o limite superior. Um crivo até 1 bilhão ocupa aproximadamente 1 GB de RAM se você usar um array de bits compactado, e quase 10 GB se for um array de booleanos padrão. Se o seu sistema tem 16 GB e você tentar rodar direto, vai estourar e o processo será matado pelo kernel. A solução prática é o crivo segmentado. Você divide o intervalo em blocos que cabem na memória e processa cada segmento separadamente. O custo adicional é pequeno — você ainda precisa do crivo base até a raiz quadrada do limite final como pré-computação — mas permite gerar tabelas de bilhões de primos em máquinas comuns. Eu uso esse método para gerar listas até 100 bilhões em um notebook com 32 GB, e o processo leva cerca de 20 minutos.
Outro ponto que causa confusão: o número 2 é o único primo par. Em qualquer implementação séria, você trata o 2 como caso especial e só iterador sobre os ímpares a partir daí. Esquecer disso não quebra o resultado, mas dobra o trabalho desnecessariamente.
👉 Clique no botão abaixo para saber mais sobre o assunto!
implementação minimalista em Python
Se você quer algo funcional rápido, aqui está uma versão que roda razoavelmente bem até alguns milhões: def crivo_eratostenes(n):
se n < 2:
retornar []
marca = [True] * (n + 1)
marca[0] = marca[1] = False
para i de 2 até int(n 0.5) + 1:
se marca[i]:
para j de i * i até n + 1 com passo i:
marca[j] = False
retornar [i para i em intervalo(2, n + 1) se marca[i]]
Para fins educacionais isso basta. Para uso real com limites maiores, substitua a lista de booleanos por um bytearray ou use a biblioteca gmpy2, que acelera tudo em ordem de grandeza porque usa aritmética de múltipla precisão otimizada em C.
onde encontrar tabelas prontas confiáveis
O OEIS (On-Line Encyclopedia of Integer Sequences) mantém a sequência A000040 com os primeiros milhares de primos atualizados e verificados. O site primento.org gera tabelas interativas até 10 milhões e permite download em CSV. Para números maiores que isso, o projeto PrimeGrid disponibiliza dados brutos de primos grandes, mas são específicos para primos de formas particulares (primos de Mersenne, primos primos gêmeos etc.), não uma tabela sequencial completa. Se o seu objetivo é criptografia, vale notar que tabelas de primos sequenciais têm utilidade limitada. algoritmos como RSA precisam de primos grandes gerados de forma probabilística, não de listas pré-computadas. Para esses casos, use geradores baseados no teste de Miller-Rabin com sementes deterministicas, como o OpenSSL oferece nativamente.
erros comuns que invalidam sua tabela sem você perceber
O mais frequente é não considerar que o início do laço de eliminação deve ser i * i, e não i * 2. Se você começar de i * 2, o resultado ainda está correto, mas o algoritmo repete trabalho já feito por primos menores e fica significativamente mais lento. A partir de i * i, todos os múltiplos menores já foram marcados por divisores menores. Outro erro comum é usar float para calcular a raiz quadrada do limite em linguagens com precisão finita. Em Python isso raramente é problema, mas em C ou JavaScript, valores próximos de limites de potências de 2 podem sofrer arredondamento e eliminar primos ou incluir compostos. Use integer square root em vez de sqrt() quando possível.
E se você precisa simplesmente consultar uma lista sem gerar nada, a tabela de número primo que eu uso diariamente é uma planilha exportada do crivo segmentado até 100 milhões, armazenada em formato binário compactado. O arquivo tem 540 MB e carregar tudo na memória leva uns 3 segundos. Para consultas pontuais, eu uso buscas binárias diretas nesse arquivo sem precisar manter o array inteiro carregado.
