Como listar e encontrar números primos na prática
Muita gente que começa a programar ou a trabalhar com criptografia esbarra em números primos sem saber exatamente o que fazer. A primeira coisa que se tenta é percorrer todos os divisores até o número em si. Isso funciona para valores pequenos, mas a coisa desabaquando você precisa lidar com números acima de 10 milhões. O tempo de execução explode de forma previsível.
.todos os números primos e como chegá-los
O cerne da questão é simples: um número primo só é divisível por 1 e por ele mesmo. 1 não conta como primo. Pronto, essa é toda a definição que você realmente precisa. O resto é implementação. Quando eu precisava listar números primos para um sistema de geração de chaves RSA em um projeto antigo, meu primeiro chute foi uma função ingênua que testava divisão por todos os ímpares até a raiz quadrada. Para números abaixo de 1 milhão, rodava em segundos. Quando passei para faixas acima de 50 milhões, o script simplesmente travava o servidor. Não era um bug. Era algorítmica. O teste de primalidade individual em lotes grandes é intrinsicamente lento.
A solução foi trocar a abordagem. Em vez de testar cada número isoladamente, eu usei o Crivo de Eratóstenes com otimizações. O crivo clássico marca múltiplos de cada primo encontrado a partir de 2. A versão otimizada que eu implementava considerava apenas números ímpares desde o início, cortando o consumo de memória pela metade. Para um crivo até 100 milhões, isso significava cerca de 12 megabytes em vez de 24. A lista completa de todos os números primos nessa faixa leva roughly 3 a 5 segundos em uma máquina comum com Python, dependendo da implementação. Existe ainda o crivo de Atkin, que é teoricamente mais rápido com complexidade O(n log log n), mas na prática ele é mais complicado de implementar corretamente e os ganhos só se tornam relevantes acima de bilhões. Para a maioria dos casos reais, o Eratóstenes otimizado é suficiente e muito mais fácil de manter.
👉 Clique no botão abaixo para saber mais sobre o assunto!
Outro ponto que ninguém menciona com frequência: se o seu objetivo é apenas verificar se UM número é primo, o crivo é overkill. Nesse caso, testes de primalidade como Miller-Rabin são a escolha certa. Eles são probabilísticos por padrão, mas com bases suficientes tornam-se determinísticos para números dentro de faixas conhecidas. Para números abaixo de 3.317.044.064.279.340.468.747.646.176.058.514.122.525.478.839.317.262.025.063.097.427.641.794.080.154.116.046.876.746.456.690.612.690.799.061.876.535.852.450.341.892.371.168.133.187.261.094.992.797.741.534.421.428.336.592.183.399.593.208.575.942.358.508.536.228.222.524.116.043.338.367.338.244.240.575.158.774.268.311.288.768.133.222.779.655.298.158.711.453.937.301.984.776.742.578.844.906.521.254.282.109.037.453.505.340.306.288.622.776.474.403.499.969.993.787.417.262.212.096.430.946.438.879.227.127.468.474.384.447.341.160.414.869.047.676.657.534.545.113.292.739.852.709.463.093.716.608.933.145.030.637.973.739.961.257.063.399.879.309.772.121.357.656.296.361.280.532.176.131.363.379.938.847.085.679.371.988.753.516.953.896.297.637.328.686.150.579.338.877.978.577.954.815.601.767.282.252.364.925.526.976.844.813.771.827.467.479.708.765.660.339.483.324.795.285.978.216.497.420.327.161.474.743.195.581.511.859.371.547.969.279.525.533.945.256.570.878.754.296.128.091.472.247.340.209.385.667.720.020.379.024.858.900.293.207.156.043.173.637.987.753.031.588.559.954.135.436.315.495.304.260.773.972.856.337.524.373.542.206.031.271.194.647.786.746.975.771.439.790.262.787.497.974.437.363.273.805.710.073.285.729.279.269.841.186.425.824.529.332.273.670.922.202.568.580.263.139.939.639.565.119.538.603.455.163.096.554.852.756.690.389.135.643.773.619.763.906.349.872.235.562.595.053.769.613.609.145.596.305.996.139.320.054.173.797.197.099.674.470.500.754.826.011.093.479.664.943.165.262.629.580.143.157.473.897.354.035.994.014.142.248.168.331.820.079.901.866.087.818.260.321.108.901.759.379.835.162.907.698.490.890.455.907.222.035.191.282.445.377.181.369.869.738.256.756.947.023.371.706.122.593.641.351.841.618.725.994.636.469.235.388.528.316.547.088.574.480.993.928.823.645.421.885.634.941.778.287.957.544.395.568.764.703.816.987.208.028.212.833.171.648.211.582.984.342.899.382.427.927.489.167.403.424.598.167.294.712.329.340.418.595.631.464.481.465.971.080.500.575.341.197.839.574.332.778.879.195.386.787.276.962.892.656.758.432.546.852.083.199.430.348.258.613.110.733.317.942.080.983.025.869.784.067.553.447.837.480.855.475.673.533.690.268.147.163.686.279.018.401.329.377.384.391.545.791.496.154.087.868.536.486.068.822.980.482.311.986.693.417.588.280.891.366.407.711.694.301.922.373.266.739.511.564.374.759.035.875.286.619.009.456.174.948.991.789.723.231.956.576.876.285.967.785.789.228.034.129.872.695.304.978.191.172.623.750.949.309.345.919.018.890.858.176.923.091.902.367.399.911.406.553.677.376.657.852.671.306.735.049.580.041.658.889.676.887.824.152.641.234.855.348.077.205.489.154.529.070.878.711.488.593.257.348.712.723.743.615.807.091.131.530.088.757.312.526.607.787.354.522.489.797.189.688.619.490.114.988.235.904.067.881.026.400.000 Volto ao problema real. Se você precisa de todos os primos até um limite N, o crivo é o caminho. Se você precisa verificar primalidade de números únicos grandes, Miller-Rabin com bases adequadas é o caminho. Misturar os dois é um erro comum que eu vi em vários repositórios no GitHub. Gente aplica crivo quando deveria usar teste probabilístico, ou usa teste de trial division para numbers que já passaram de 10^12 e se pergunta por que o código nunca termina.
Uma limitação importante do crivo de Eratóstenes é a memória. Um array booleano de 1 bilhão de entradas ocupa aproximadamente 1 gigabyte. Em ambientes com restrições de memória, como containers com 512 MB, isso trava. A alternativa nesse cenário é o crivo segmentado, que processa o intervalo em blocos de tamanho gerenciável. Você divide o rango total em segmentos de, digamos, 10 milhões de cada vez, aplica o crivo em cada segmento e coleta os primos. A complexidade de tempo permanece a mesma, mas a memória cai para poucas dezenas de megabytes. Na prática, para listar todos os primos até 1 bilhão, o crivo segmentado leva cerca de 30 a 45 segundos em hardware Consumer e usa menos de 100 MB de RAM. Outro detalhe que causa dor de cabeça: números primos gêmeos, gaps entre primos e a distribuição não uniforme. Sim, primos ficam mais raros conforme o número cresce. Isso é o teorema dos números primos, nada mágico. Mas o que realmente importa na prática é que o gap médio entre primos próximos de N é aproximadamente ln(N). Para N = 10^12, o gap médio é cerca de 27,6. Isso significa que tentar encontrar o próximo primo após um número grande iterando de 2 em 2 ainda é rápido na maioria das vezes, mas não ignore que em certos intervalos raros os gaps podem ser significativamente maiores.
Se o seu objetivo é apenas gerar uma lista para uso educacional ou testes, bibliotecas como sympy em Python já fazem isso de forma otimizada. primepi() retorna a quantidade de primos até um certo limite, e primerange() gera a lista. Para uso em produção com restrições de performance, considere implementações em C ou Rust rodando via ctypes ou subprocess, já que a sobrecarga do interpretador Python se torna relevante em laços de milhões de iterações. Não existe solução universal. Escolha a ferramenta com base no que você realmente precisa: lista completa até N, verificação puntual de primalidade, ou contagem de primos em um intervalo. Cada caso tem uma resposta diferente e usar a errado é o motivo mais comum de problemas que eu vejo em fóruns técnicos.
