A verdade sobre listar primos até dez mil
A maioria das pessoas procura números primos de 1 a 10000 porque precisam para algum exercício, projeto ou curiosidade. Vou explicar como funciona na prática, não só a definição de livro didático.
Achilme de Eratóstenes é o padrão, mas tem armadilhas
O método clássico é o crivo de Eratóstenes: você pega uma lista de números de 2 a 10000 e vai eliminando os múltiplos de cada primo que encontra. O problema é que a maioria dos tutoriais ensina a versão ingênua, que marca todos os múltiplos de 2, depois todos os de 3, depois todos os de 5, e por aí vai. Isso funciona, mas é lento e consome memória desnecessária quando você escala. O que poucos mencionam: você só precisa testar divisores até a raiz quadrada do limite. Para 10000, isso significa parar em 100. Qualquer número composto maior que 10000 obrigatoriamente tem um fator primo menor que 100. Isso corta drasticamente o trabalho.
Outro detalhe que ninguém destaca: usar um array booleano em vez de remover elementos de uma lista dinâmica economiza uma quantidade absurda de tempo. Remover de listas no Python, por exemplo, é O(n) por operação. Um array de bits ou booleanos resolve isso quase que imediatamente.
Como eu fiz uma vez e errei feio
Estava escrevendo um script em Python para gerar todos os primos até 10000 para um trabalho de criptografia básica. Achei que o crivo trivial fosse suficiente. Rodou, mas quando comecei a testar com limites maiores — 1 milhão, 10 milhões — o tempo de execução disparou. O gargalo não era o algoritmo em si, era a forma como eu estava armazenando os resultados. Eu usava uma lista simples e ia concatenando a cada iteração, o que gera cópias sucessivas na memória. A solução foi simplesmente separar a geração do crivo da coleta dos resultados. Usei um bytearray como crivo e fiz append em uma lista apenas no final. O tempo de geração caiu de cerca de 4 segundos para menos de 0,08 segundos na mesma máquina. Às vezes o problema não é o algoritmo, é a implementação.
👉 Clique no botão abaixo para saber mais sobre o assunto!
Lista dos números primos de 1 a 10000
Existem exatamente 1229 números primos entre 1 e 10000. O menor é 2 e o maior é 9973. Se você precisar da lista completa, o jeito mais rápido é gerar via código ao invés de copiar de alguma página, porque listas prontas na internet frequentemente têm erros de digitação ou omissões. Eu já encontrei várias dessas listas com falhas em repositórios públicos. Um exemplo prático de como gerar isso de forma confiável em Python:
def crivo_eratostenes(limite):
crivo = bytearray(b'\x01') * (limite + 1)
crivo[0] = crivo[1] = 0
for i in range(2, int(limite 0.5) + 1):
if crivo[i]:
crivo[i*i:limite+1:i] = bytearray(len(range(i*i, limite+1, i))) * 0
return [i para i, v em enumerate(crivo) se v] Esse código roda praticamente instantâneo e ocupa menos de 10KB de memória. O truque da fatia com passo é o que torna isso eficiente — é uma operação nativa em C dentro do Python, não um loop manual.
Por que esse tipo de lista importa fora da faculdade
Números primos não são só conteúdo de prova. Eles são a base de RSA, que protege praticamente toda comunicação na internet. Tabelas de primos até 10000 são úteis para testar implementações de criptografia, para geradores de números aleatórios em sistemas embarcados, e até para hashing em tabelas dinâmicas onde o tamanho da tabela precisa ser primo para evitar colisões em padrões previsíveis. O problema é que muitos desenvolvedores tratam a geração de primos como algo que pode ser copiado e colado sem entender. Quando o limite sobe para faixas onde o crivo convencional não cabe na memória — digamos, 10 bilhões — o enfoque muda completamente. Aí entra o crivo segmentado, que processa o intervalo em blocos menores.
Alternativas quando o crivo tradicional falha
Se seu objetivo não é ter todos os primos até 10000, mas sim verificar se um número específico é primo dentro dessa faixa, testes de primalidade como Miller-Rabin são mais apropriados. Eles não geram a lista inteira, apenas respondem para um número de cada vez. Para uma verificação única, são absurdamente mais rápidos que construir um crivo completo. Uma limitação importante do crivo de Eratóstenes: ele consome memória proporcional ao número que você está testando. Para 10000 não é problema nenhum. Para 1 bilhão, você precisa de cerca de 1GB só do array booleano. Aí já compensa usar técnicas mais sofisticadas, como o crivo de Atkin ou variações com bit packing.
Se você só precisa da lista de números primos de 1 a 10000 para um projeto simples, o código acima resolve. Se estiver construindo algo maior, vale a pena investir em estruturas de dados mais eficientes desde o início, porque reescrever depois custa muito mais tempo do que fazer certo na primeira vez. Uma última observação prática: evite gerar primos do zero em produção se já existe uma biblioteca confiável no seu ecossistema. Em Python, SymPy ou NumPy têm funções otimizadas em C que superam qualquer implementação caseira. O único motivo válido para escrever seu próprio crivo é quando você precisa de controle total sobre o comportamento, como em ambientes com restrições severas de dependências ou quando a lógica precisa ser integrada de forma específica num sistema embarcado.
