Todos Os Numeros Primos

Como listar todos os números primos até um determinado limite

O método mais direto para gerar uma lista completa de primos é o Crivo de Eratóstenes. Você não precisa de lógica complicada. O problema aparece quando você tenta aplicar isso sem entender onde ele quebra. O algoritmo funciona assim: cria um array booleano de 0 até N, marca 0 e 1 como não primos, depois percorre de 2 até a raiz quadrada de N. Quando encontra um número ainda marcado como primo, marca todos os seus múltiplos como compostos. O que sobrar marcado como verdadeiro são os primos.

Gerando todos os numeros primos em Python

def crivo_eratostenes(n):
    if n 2:
        return []
    
    marcar = [True] * (n + 1)
    marcar[0] = marcar[1] = False
    
    for i in range(2, int(n0.5) + 1):
        if marcar[i]:
            for j in range(i * i, n + 1, i):
                marcar[j] = False
    
    return [i for i, val in enumerate(marcar) if val]



Isso é funcional para N até alguns milhões. Passa disso e você começa a sentir dor de cabeça com memória. O array booleano consome cerca de 1 byte por entry na maioria das implementações Python. Para N=100 milhões, isso é 100MB só no array, sem contar o overhead do interpretador. Uma coisa que muita gente não considera: o crivo tradicional não é segmentado. Se você precisa de primos entre 1 bilhão e 1 bilhão e cem milhões, executar o crivo inteiro até 1.100.000.000 é desperdício. O crivo segmentado resolve isso dividindo o intervalo em blocos que cabem no cache L1 ou L2 da CPU. Eu tive um problema específico há uns dois anos rodando uma validação de certificados que exigia primos acima de 10^12. O crivo normal simplesmente não entrava na memória disponível. A solução foi implementar um crivo segmentado com um pré-crivo até raiz quadrada do limite superior. Pré-cravo até ~1.000.000 para obter os primos-base, depois usar cada um deles para marcar segmentos de 10^7 números de cada vez no intervalo alvo. Reduziu o uso de memória de gigabytes para alguns megabytes. A velocidade caiu cerca de 30% comparado ao crivo completo, mas foi a única forma de rodar dentro dos constraints.
Pitfalls comuns

O erro mais frequente é começar a marcar múltiplos a partir de 2*i em vez de i*i. Para i=2, tudo bem. Para i=97 já é desperdício de operação. Começar de i*i economiza marcadores redundantes sem impacto prático para ranges pequenos, mas para ranges grandes isso faz diferença medível. Outro erro: usar variáveis inteiras normais sem verificar overflow. Em C++ ou Rust, um produto i*i pode estourar um int de 32 bits se i passar de 46340. Em Python isso não acontece porque o idioma escala automaticamente, mas em linguagens com tipagem fixa é uma armadilha clássica. Se você está numa linguagem sem garbage collector e precisa de performance extrema, considere representar o array como bits ao invés de bytes. O crivo bit-packed usa 8x menos memória. A desvantagem é que as operações de acesso ficam ligeiramente mais caras por causa das máscaras de bits, mas na prática o ganho de cache hit rate compensa sobra.
Veja os Detalhes Completos


Exemplos De Números Primos : Quais são os Números Primos? – GVPJXQ

Quando o crivo não é a resposta

Se o seu objetivo é apenas testar se um número específico é primo, o crivo é overkill. Um teste de Miller-Rabin com bases determinísticas para 64-bit (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37) é muito mais rápido para checks pontuais. Ele roda em tempo logarítmico e é exato até 2^64. Para gerar o próximo primo após um número grande N, use um teste de primalidade em sequência a partir de N+1. Os primos são suficientemente densos (pela função pi(x) ~ x/ln(x)) que você raramente vai testar mais de 100-200 números consecutivos antes de encontrar um primo, mesmo em ranges altos. O crivo também falha silenciosamente se você pedir primos até um N negativo ou zero. Sempre trate o caso base. Um return vazio ou uma exception clara evita bugs difíceis de rastrear em pipelines maiores.
O que você precisa saber na prática

Para projetos reais, não reimplemente o crivo do zero se puder evitar. Bibliotecas como sympy em Python ou GMP::nextprime em C já estão otimizadas. O problema é que sympy carregada inteira pesa cerca de 5MB e demora alguns segundos para importar. Se você só precisa de primos e nada mais, vale a pena escrever uma versão minimalista em C e chamar via subprocess ou ctypes. O ganho em tempo de start-up e uso de memória costuma justificar o esforço. Outro detalhe prático: a ordem dos primos gerados pelo crivo é sempre crescente. Se você precisa embaralhar ou processar em paralelo, precisará de uma etapa extra. Distribuir o trabalho entre threads usando crivo segmentado é viável, mas cada thread precisa do mesmo conjunto de primos-base, então há overhead de distribuição que nem sempre vale a pena para ranges abaixo de 10^9. A lista completa de primos até 10^8 tem 5.761.455 elementos. Até 10^9 tem 50.847.534. O tamanho da saída cresce rápido e muitas vezes é o verdadeiro gargalo — não o cálculo em si, mas a escrita ou transmissão dos resultados.