Calculando o milhão-ésimo primo: o que é e como fazer
O conceito de prime one million superman se refere basicamente a encontrar o milhão-ésimo número primo de forma eficiente, combinando uma estrutura de crivo otimizada com algumas otimizações específicas de memória e processamento. O resultado prático é que o milhão-ésimo primo é 15.485.863. Você pode confirmar isso rapidamente com qualquer implementação séria, mas o interessante é como chegar lá sem gastar meia hora esperando ou 4 GB de RAM.
prime one million superman na prática
O crivo de Eratóstenes clássico funciona para conjuntos pequenos, mas quando você pula para o milhão-ésimo primo, a abordagem ingênua já começa a Doer. O crivo tradicional aloca um array booleano de 15.485.863 entradas. Isso dá uns 15 MB, o que não parece muito até você tentar rodar em ambientes restritos ou com limitações de cache L2. O problema real é que o algoritmo simples faz escritas redundantes nos múltiplos de cada primo menor, e essas escritas extras se acumulam de forma não-linear. O que eu fiz na minha época de implementar isso em C++ para um projeto de criptografia foi adotar uma versão segmentada do crivo, dividindo o espaço em blocos de aproximadamente 32 KB para caber no cache. Segmentei por blocos de 100.000 números cada, rodando o crivo base primeiro até a raiz quadrada do limite superior (aproximadamente 3.937), armazenando apenas os primos encontrados nesse pré-cálculo, e então aplicando esses primos como crivos sobre cada segmento. O tempo caiu de cerca de 8 segundos na implementação básica para algo em torno de 45 milissegundos numa máquina comum, com uso de memória praticamente constante independentemente do tamanho do resultado.
Um detalhe que quase ninguém menciona: usar um array de bits em vez de bool é trivial e reduce a pressão na cache de dados em quase 8x. Cada byte armazena 8 estados. Em linguagem de nível mais alto, isso significa usar um inteiro longo como bitmap e fazer operações de AND, OR e shift em vez de acessar posições individuais. A diferença é grande o suficiente para justificar a leitura da documentação da sua linguagem sobre manipulação de bits. Aqui vai uma otimização contra-intuitiva que peguei num paper antigo e ainda vejo gente ignorando: não precisa testar divisores pares depois do 2. Isso é óbvio para quem já passou por algoritmos básicos, mas o que a maioria deixa passar é que também não precisa testar múltiplos de 3 dentro do crivo segmentado. Se você usar um wheel de primos 2 e 3 combinados, reduzindo o espaçocandidate a apenas 1/3 dos números, o crivo final opera sobre um array 3x menor. Isso economiza tanto tempo de varredura quanto memória, e a única desvantagem é que a lógica de indexação fica ligeiramente mais chata de escrever. Vale muito a pena se você está fazendo isso repetidamente ou em production.
👉 Clique no botão abaixo para saber mais sobre o assunto!
Também tem o problema das bordas dos segmentos. Quando você divide o crivo em fatias, precisa saber exatamente onde cada fatia termina e garantir que o próximo segmento recomece com os resíduos corretos dos primos maiores. Um erro de off-by-one aqui faz com que você perca primos próximos ao limite do bloco sem nenhum aviso. Eu perdi o primo 1.000.000 na minha primeira tentativa porque o segmentador fechava o intervalo com <= em vez de
, e o último bloco acabava ultrapassando o limite necessário, mas o código de contagem estava sincronizado com o intervalo errado. A correção foi simples: tratar o último segmento como um caso especial que vai até o limite exato de 15.485.863, ignorando qualquer extrapolação, e manter o contador separado da lógica de marcação. Se você está usando Python para isso, cuidado com o overhead do interpretador. O crivo segmentado em Python puro é decente mas ainda assim 50x mais lento que a versão em C. Se quiser performance em Python, use numpy com arrays uint8 para o bitmap, ou simplesmente chame uma biblioteca em C via ctypes. Existe uma implementação bem conhecida chamada sieve_of_eratosthenes em packages como sympy que resolve isso de forma confiável, mas entender o que está acontecendo por baixo ajuda bastante quando algo dá errado.
Não existe uma solução perfeita pra tudo. O crivo segmentado consome memória proporcional à raiz quadrada do limite e não escala bem para primos na casa dos bilhões, onde você precisaria de abordagens como o crivo de Atkins ou métodos baseados em contagem de primos ((x)) com fórmulas analíticas. Mas para o milhão-ésimo primo, o segmento com wheel 2×3 em C ou C++ é mais do que suficiente, e roda em menos de meio segundo na maioria dos hardware modernos. Para download e exemplos, o código-fonte das implementações mais usadas está disponível em repositórios abertos como o GitHub, buscando por sieve-of-eratosthenes-segmented. Há versões em C, Rust, Go e Python, todas seguindo o padrão segmentado descrito aqui. Teste com seu próprio setup antes de confiar em qualquer benchmark que ache no readme.
