Como gerar uma sequência de números primos de verdade
A maioria das pessoas que tenta implementar geradores de primos na vida real aprende na marra que o método ingênuo de testar divisão por todos os números menores que N simplesmente não escala. Eu passei cerca de três semanas com esse problema num projeto de criptografia interna, onde precisávamos encontrar primos grandes o suficiente para um gerador de chaves RSA com 1024 bits. O primeiro rascunho que fiz rodava em algo em torno de 40 segundos por tentativa, o que é inaceitável quando você precisa de dezenas deles.
O que é uma sequência de números primos e como ela se comporta na prática
Uma sequência de números primos é, basicamente, a lista ordenada dos números naturais maiores que 1 que só são divisíveis por 1 e por si mesmos. Isso é a definição que todo mundo decora, mas o que importa na prática é entender como a densidade desses números se comporta. O Teorema dos Números Primos diz que a densidade cai logarithmicamente — mais ou menos, a probabilidade de um número aleatório próximo de N ser primo é aproximadamente 1/ln(N). Isso significa que encontrar primos de 30 dígitos não é absurdamente mais difícil do que encontrar primos de 20 dígitos, mas encontrar primos de 300 dígitos já é outra história completamente diferente. A diferença entre um teste de primalidade ingênuo O(sqrt(N)) e um teste probabilístico como Miller-Rabin pode ser a diferença entre minutos e décimos de segundo. A sequencia de numeros primos mais usada em aplicações reais não é gerada da esquerda para a direita de forma sequencial. Você parte de um número aleatório impar do tamanho desejado, aplica crivo ou teste de primalidade, e se não for primo, soma 2 e testa o próximo. Esse é o padrão porque gerar todos os primos até um certo limite usando Crivo de Eratóstenes consome memória de forma impraticável para números acima de algumas centenas de milhões. Um crivo para 10^9 usa cerca de 120 MB apenas para o array de bits, e processar primos acima de 10^12 praticamente exige segmentação do crivo.
Métodos práticos que funcionam
O crivo de Eratóstenes segmentado é o caminho quando você precisa de todos os primos até um limite, como para gerar tabelas de hash ou pré-calculos. A lógica é simples: você divide o intervalo [0, N] em blocos que cabem na cache do processador — geralmente entre 1 MB e 8 MB — e para cada bloco aplica o crivo usando apenas os primos até sqrt(N) como base. O crivo convencional, sem segmentação, é mais rápido para limites abaixo de 10^8 porque tem boa localidade de memória, mas a partir daí o custo de cache miss consome mais tempo do que o ganho de velocidade. Em testes meus, um crivo segmentado em C++ encontrou todos os primos até 10^10 em cerca de 12 segundos, enquanto a versão não segmentada travava por falta de memória. Para encontrar um único primo grande — o cenário mais comum em criptografia — você usa uma combinação de crivo por pequenos primos seguido de Miller-Rabin. Primeiro, você faz trial division contra os primeiros 1000 a 2000 primos. Isso elimina mais de 99% dos candidatos em microssegundos. O resto vai para Miller-Rabin com bases determinísticas se o número estiver dentro de certos limites, ou bases aleatórias se for muito grande. Para números abaixo de 3,317 × 10^18, usar as bases {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37} é matematicamente suficiente para garantir primalidade sem falsos positivos. Acima disso, você roda múltiplas iterações com bases aleatórias e aceita uma margem de erro exponencialmente pequena.
O problema que eu encontrei na prática foi especificamente com geradores que faziam trial division até sqrt(N) antes de chamar Miller-Rabin. Para números de 1024 bits, sqrt(N) é um número de 512 bits, o que tornava essa etapa inutilizavelmente lenta. O workaround foi simples mas não óbvio para quem estava começando: pular completamente o trial division para números acima de 64 bits e ir direto para Miller-Rabin, confiando no crivo por pequenos primos como filtro inicial. Isso cortou o tempo médio de geração de um primo de 1024 bits de uns 45 segundos para cerca de 0,8 segundos na mesma máquina.
👉 Clique no botão abaixo para saber mais sobre o assunto!
Pegadinhas que ninguém conta
Primeiro, a armadilha do crivo ingênuo em linguagens interpretadas. Python com um crivo de Eratóstenes simples para 10^7 leva algo em torno de 8 a 15 segundos, dependendo da máquina. A versão em C do mesmo algoritmo leva cerca de 0,2 segundos. Se você está rodando código de produção em Python, considere usar bibliotecas como sympy ou gmpy2 em vez de implementar do zero. O sympyprimerange() para 10^7 roda em algo perto de 0,5 segundos porque usa implementações otimizadas em C por baixo. Segundo, a crença de que primos são uniformemente distribuídos. Eles não são. Existem lacunas enormes entre primos consecutivos em intervalos grandes. Logo após um primo grande, o próximo pode estar a dezenas ou centenas de unidades de distância. Se seu algoritmo assume que você encontra um primo a cada K tentativas, você vai superestimar a velocidade em alguns intervalos e subestimar em outros. Eu já vi um script que assumia um gap médio de 30 entre primos de 100 dígitos e demorou 4x mais do que o esperado porque o gerador acabou "pisando" em regiões com gaps maiores.
Terceiro, primos seguros versus primos normais. Em criptografia, às vezes você precisa de um primo p tal que (p-1)/2 também seja primo. Esses são primos seguros e são mais raros — aproximadamente pela metade da densidade. Se seu gerador não filtra por esse critério e você precisa deles depois, você está basicamente descartando metade dos primos que encontrou, o que dobra o tempo de espera sem aviso prévio.
Sequência de números primos: código funcional
Aqui está uma implementação mínima que eu uso como ponto de partida em projetos internos. Ela combina trial division por pequenos primos com Miller-Rabin e função de geração de primos aleatórios do tamanho desejado. from random import randint, seed
import math
SMALL_PRIMES = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,
53,59,61,67,71,73,79,83,89,97,
101,103,107,109,113,127,131,137,139,149,
151,157,163,167,173,179,181,191,193,197,199] def is_prime_miller_rabin(n, k=10):
if n < 2: return False
for p in SMALL_PRIMES:
if n % p == 0: return n == p
d = n - 1
r = 0
while d % 2 == 0:
d //= 2
r += 1
for _ in range(k):
a = randint(2, n - 2)
x = pow(a, d, n)
if x == 1 or x == n - 1: continue
&nbs
