Como construir e usar uma tabela de números primos na prática
Você provavelmente já viu uma tabela de números primos em algum material didático ou planilha. A coisa mais útil que posso dizer logo de cara é: não tente montar essas tabelas de cabeça ou testando divisão por todos os números menores. Existe um método antigo, simples e que ainda é o padrão da indústria para ranges até algumas centenas de milhões, e é esse que eu recomendo.
algoritmo da criva de eratóstenes
O algoritmo funciona assim: você cria um array de verdadeiros de tamanho N, marca 0 e 1 como não primos, depois itera de 2 até a raiz quadrada de N. Para cada i que ainda está marcado como primo, você marca todos os múltiplos de i a partir de i*i como não primos. O que sobrar são os primos. A complexidade é O(n log log n), o que para n=10 milhões roda em cerca de 80 a 120 milissegundos em uma máquina comum com Python otimizado ou C. Em Python puro, esse mesmo cálculo pode levar 3 a 5 segundos, então a linguagem importa bastante.
Um detalhe que muita gente erra: você começa a crivar a partir de i*i, não de 2*i. Se começar de 2*i, o algoritmo ainda funciona, mas você desperdiça work porque múltiplos menores que i*i já foram marcados por fatores menores. Em ranges grandes, isso pode significar 30 a 40% de tempo extra desnecessário.
tabela de número primo
Uma tabela de número primo nada mais é do que um array ou lista contendo todos os primos até um limite determinado. O formato mais comum é um vetor booleano (a criva em si) ou um vetor de ints contendo apenas os primos. A escolha entre um e outro depende do que você vai fazer depois. Se o objetivo é testar se um número é primo rapidamente, o vetor booleano é melhor. Consultas são O(1). Se o objetivo é iterar sobre os primos ou usá-los como fatores em fatoração, o vetor compactado (só primos) economiza memória e é mais rápido de percorrer.
No range de 0 a 10 milhões, o vetor booleano ocupa cerca de 10 MB se usar um byte por entrada, ou 1,25 MB se usar bits. O vetor compactado com apenas os 664.579 primos nesse intervalo ocupa cerca de 2,6 MB em ints de 32 bits. Então o vetor booleano pode ser mais econômico em memória para ranges médios, o que é contra-intuitivo para quem acha que listar só os primos sempre ocupa menos.
👉 Clique no botão abaixo para saber mais sobre o assunto!
um problema real que encontrei
Eu precisava gerar primos até 500 milhões para um sistema de geração de chaves RSA em um servidor com 4 GB de RAM. A criva padrão em um único array booleano não cabia na memória. O workaround foi dividir o range em blocos de 30 milhões que cabiam no cache L3 do processador, crivar cada bloco usando os primos até sqrt(500 Milhão) como sementes, e concatenar os resultados. Os primos até sqrt(500 Milhão) — que é cerca de 22.360 — cabem facilmente em um vetor pequeno. Eu gerei esses primos primeiro com uma criva normal, depois usei eles para segmentar a criva principal. O processo inteiro levou uns 4 minutos, contra os 12+ segundos que daria se a criva inteira cabesse na memória. A versão segmentada é mais lenta por causa da sobrecarga de gestão de blocos, mas é a única opção viável quando o range ultrapassa a memória disponível.
armadilhas comuns
Primeiro, muitos programadores esquecem que números pares maiores que 2 não precisam nem ser considerados. Skipar todos os pares pela metade reduz tempo e memória em 50%. É o ajuste mais barático que existe. Segundo, usar inteiros para o vetor booleano em vez de bits ou byte arrays. Em Python, uma lista de booleans com 100 milhões de entradas consome cerca de 900 MB. Um array de bytes do módulo array ou um bytearray ocupa 100 MB. A diferença é gigante.
Terceiro, confiar que a criva funciona bem para testar primalidade de números individuais muito grandes. Se você precisa testar se um número de 100 dígitos é primo, a criva não é a ferramenta certa. Você usa Miller-Rabin ou Lucas-Lehmer. A criva serve para enumerar primos até um limite, não para testar primalidade de números arbitrários grandes.
quando a tabela simplesmente não funciona
Se você precisa de primos acima de 10^12, a criva de Eratóstenes clássica não é viável sem hardware robusto e otimizações avançadas de segmentação e paralelismo. Nesse regime, a abordagem padrão muda para testes probabilísticos de primalidade com sementes determinísticas, combinados com sieve de Atkins ou sieves wheel para pré-filtragem. Para a maioria dos casos práticos — criptografia educacional, exercícios de programação, geração de chaves pequenas para protótipos — uma criva até 10^8 ou 10^9 resolve. Acima disso, você já está no território de projetos que exigem considerações sérias de engenharia.
O código base em Python seria algo como um bytearray de tamanho N+1, inicializado com 1s, depois dois loops aninhados marcando os múltiplos. Em C ou Rust, o mesmo algoritmo roda 10 a 50 vezes mais rápido devido à ausência de overhead de interpretação e à melhor localização de cache. Se o desempenho importa, escolha a linguagem correta desde o início.
