Calcular uma sequencia de numeros primos até 100 mil com um simples loop é perda de tempo
Vou direto ao ponto. Se você precisa gerar uma sequência de números primos, o crivo de Eratóstenes é o método que praticamente todo mundo usa e, na maioria dos cenários, é o mais eficiente de fato. A ideia é simples: criar um array booleano de 0 a N, marcar todos os múltiplos de cada primo encontrado como compostos, e o que sobrar como verdadeiro é primo. Em Python, uma implementação básica roda em menos de 50 milissegundos para N = 1 milhão numa máquina comum. O problema é que a literatura ensina o crivo da forma ingênua e muita gente copia isso sem pensar. Eu já vi script rodando por 40 segundos pra chegar em 10 milhões quando uma otimização trivial corta pra 2 segundos. O segredo é não testar divisores, só marcaremos múltiplos a partir do quadrado do primo. Começar a marcação a partir de i*i já elimina metade das operações. Depois, pular os pares e usar um stride de 2*i para andar nos múltiplos ímpares reduz ainda mais.
como gerar uma sequencia de numeros primos de forma pratica
Aqui vai um código que eu uso no dia a dia. Não é luxo, é funcional: def sieve(limit):
if limit 2:
return []
is_prime = [True] * (limit + 1)
is_prime[0] = is_prime[1] = False
for i in range(2, int(limit0.5) + 1):
if is_prime[i]:
for j in range(i * i, limit + 1, i):
is_prime[j] = False
return [i for i, v in enumerate(is_prime) if v]
Para limites acima de 100 milhões, esse crivo simples começa a sofrer com memória. Um array booleano de 100 milhões de entradas ocupa cerca de 100 MB. Se você subir pra 1 bilhão, são 1 GB. Dependendo do contexto, isso já pesa. A solução aqui é usar o crivo segmentado, que processa blocos de tamanho fixo na memória. Com um segmento de 32 mil entradas, você consegue limitar o uso de memória a poucos megabytes enquanto gera primos de qualquer faixa arbitrária. Um detalhe que quase ninguém menciona: se você só quer saber se um número é primo e não precisa da sequência completa, teste de primalidade Miller-Rabin com bases fixas é mais rápido para números grandes do que qualquer crivo. Para números abaixo de 3.317 mil milhões, basta testar com bases 2, 7 e 61. É suficiente para a maioria dos usos práticos em criptografia introdutória e competições de programação.
👉 Clique no botão abaixo para saber mais sobre o assunto!
Chegou um dia em que eu precisei validar uma sequência de primos gerada por uma biblioteca externa contra a minha própria implementação. A biblioteca dizia que o 999.999.937 era primo. O crivo confirmou. Mas o número anterior, 999.999.931, estava sendo listado como composto pela API. Eu gastei umas três horas rastreando o erro. O problema era que a biblioteca usava um tipo de dado de 32 bits para o índice interno e havia um overflow silencioso quando o limite ultrapassava 2³¹. A correção foi simplesmente trocar para um tipo de 64 bits e adicionar um teste de fronteira antes de chamar a função. Se você trabalha com primos acima de 2 bilhões, verifique sempre o tipo de dado que a ferramenta usa por baixo. Outro ponto que vale saber: sequências de primos não têm padrão periódico. Isso parece óbvio, mas gente tenta ajustar polinômios e séries para prever o próximo primo com base nos anteriores. Não funciona. A distribuição segue a função logística inversa do teorema dos números primos, que estima que a densidade de primos perto de N é aproximadamente 1/ln(N). Para N = 10 milhões, a cada 16 números você espera encontrar um primo. Para N = 1 trilhão, a cada 230 números. A fórmula é útil para dimensionar quanto tempo um algoritmo vai levar, mas não serve para prever quais números específicos serão primos.
Se o objetivo é apenas consultar primos frequentemente, como em um sistema que precisa verificar identidade de usuário baseada em resíduos modulares, considere pré-computar a sequência e salvar em arquivo binário. Ler de disco é ordens de grandeza mais rápido do que recalcul a cada execução. Um arquivo de 1 milhão de primos em formato compacto cabe em cerca de 7 MB. O tempo de carga é inferior a 10 milissegundos na maioria dos SSDs modernos. Há ainda a possibilidade de usar o crivo de Atkins se você estiver lidando com limites muito altos e memória disponível não for o gargalo. Ele é mais complexo de implementar e tem constantes maiores, o que significa que para limites menores que 10 milhões o crivo de Eratóstenes otimizado é mais rápido na prática. Só vale a pena considerar Atkins acima disso, e mesmo assim o ganho é marginal, algo entre 15% e 25% em velocidade bruta.
Se você está começando agora e quer apenas uma referência rápida, o site primes.utm.edu mantém tabelas atualizadas dos maiores primos conhecidos e uma seção educacional sólida. Para quem precisa de uma biblioteca pronta, a gmpy2 ou a sympy já implementam crivos eficientes em Python. A diferença é que elas abstraem os detalhes de baixo nível, o que é bom para produtividade mas ruim se você precisar depurar algum comportamento estranho. Nesses casos, ter uma implementação própria pelo menos como referência de teste ajuda bastante. A parte mais chata na prática é lidar com bordas. O número 2 é primo e é o único primo par. Qualquer implementação que assuma que primos são todos ímpares vai falhar no primeiro caso de teste. O número 1 não é primo. Isso parece bobo, mas em código legado eu já vi gente tratando 1 como primo e a contagem errada se propagando por horas de debug.
