O que você realmente precisa saber antes de escrever qualquer código
Se você está procurando uma lista pronta de números primos, há geradores online que fazem isso em segundos. Se precisa implementar do zero, existem nuances que a maioria dos tutoriais ignora. A diferença entre um código que roda em 0,2 segundos e um que trava a memória depende de como você estrutura o problema. O método mais eficiente para encontrar todos os primos até um limite N é o Crivo de Eratosthenes. A lógica é simples: começa com uma lista de booleanos, marca todos os múltiplos de cada primo encontrado e sobram os verdadeiros. Parece fácil porque é fácil no papel. Na prática, a escolha da representação e o gerenciamento de memória mudam completamente o desempenho.
Implementação prática da sequência de números primos
Aqui está uma versão otimizada que funciona bem para limites até 10 milhões: Python:
def crivo_eratostenes(n):
if n 2:
return []
sieve = bytearray([1]) * (n + 1)
sieve[0:2] = b'\x00\x00'
for p in range(2, int(n0.5) + 1):
if sieve[p]:
sieve[p*p : n+1 : p] = b'\x00' * len(sieve[p*p : n+1 : p])
return [i for i, is_prime in enumerate(sieve) if is_prime]O uso de bytearray em vez de uma lista de bools reduz a pegada de memória em aproximadamente 8 vezes. Para n = 10.000.000, isso significa cerca de 10 MB em vez de 80 MB. A fatia com passo [p*p : n+1 : p] é muito mais rápida que um loop for porque é executada em C puro pelo interpretador Python. Para limites acima de 10^9, o crivo simples não cabe na RAM. Nesse caso, o Crivo Segmentado é necessário. Ele processa o intervalo em blocos de tamanho fixo (geralmente 32 KB a 1 MB). Cada bloco é inicializado, marcado pelos primos básicos (encontrados previamente até N) e descartado. Isso permite operar com memória constante independentemente do tamanho de N.
👉 Clique no botão abaixo para saber mais sobre o assunto!
Um problema real que encontrei
Em um projeto recente, precisei gerar todos os primos até 10^10 para testar distribuições em intervalos específicos. O crivo segmentado funcionou bem, mas o gargalo apareceu na fase inicial: gerar os primos até (10^10) = 10^5. Esse subconjunto pequeno parece irrelevante, mas a maneira como você o calcula afeta tudo que vem depois. A solução foi usar o crivo clássico para os 10^5 primos básicos primeiro, depois armazená-los em um array compacto de int32. O tempo total caiu de cerca de 12 segundos para aproximadamente 3 segundos em minha máquina. Não é uma otimização dramática em termos relativos, mas faz diferença quando você executa o processo múltiplas vezes durante testes.
O que os tutoriais não contam
O Crivo de Eratosthenes tem uma complexidade teórica de O(n log log n), mas essa análise assume memória ideal e acesso uniforme. Na prática, o padrão de acesso à memória é o fator dominante. O crivo padrão tem excelente localidade de cache para divisores pequenos — os múltiplos de 2, 3 e 5 são escritos consecutivamente nas primeiras iterações. Conforme p cresce, os saltos ficam maiores e o cache efficiency cai. Outro ponto ignorado: o crivo não é o melhor método se você só precisa testar se um número isolado é primo. Para teste de primalidade de um único número grande, o teste de Miller-Rabin é orders of magnitude mais rápido. O crivo só se torna vantajoso quando você precisa de múltiplos primos dentro de um intervalo.
A armadilha comum é tentar usar o crivo para gerar primos acima de 10^12 em uma máquina comum. Ele simplesmente não vai funcionar — o uso de memória excede o disponível e o programa é terminado pelo kernel. Nesses casos, ou se trabalha com primos esparsos de tamanho arbitrário, a abordagem correta é usar crivo segmentado com múltiplas threads ou recorrer a bibliotecas especializadas como PrimeGrid ou GMP-ECM para números com mais de 20 dígitos.
Downloads e ferramentas
Se precisa de uma lista pronta de primos, o site primes.utm.edu mantém listas verificadas até 10^16. Para rodar localmente, o código acima pode ser salvo como um arquivo .py e executado diretamente. Para C++ ou Rust, a lógica é idêntica mas com ganho de performance de 10x a 50x dependendo do limite. Uma observação final: se o objetivo é apenas a sequência de primos para fins educacionais ou competitivos, manter os primos em uma lista é suficiente. Mas se você for fazer operações pesadas como fatoração, calcular funções totais de Euler em larga escala, ou trabalhar com criptografia, considere pré-computar os primos e armazená-los em formato binário. Ler de disco é mais rápido do que recalculá-los toda vez.
