Números Primos De 0 A 100

Como encontrar os primos entre 0 e 100 na prática

Quem começa a mexer com números primos normalmente pega uma lista pronta na internet e copia. Eu também fiz isso no começo, até perceber que saber montar a lista do zero economiza tempo quando o computador não tá acessível ou quando você precisa explicar o raciocínio para outra pessoa. O método mais direto é o Crivo de Eratóstenes. Você escreve os números de 1 a 100 numa tabela, marca o 1 porque ele não é primo, pega o 2, risca todos os múltiplos dele a partir de 4, depois pega o próximo não riscado, que é o 3, e risca os múltiplos dele a partir de 9. Continua assim com o 5 e com o 7. Quando chega no 11, a raiz quadrada de 100, você já parou. O resto que sobrou sem marcação são os primos. O crivo é eficiente pra faixas pequenas como essa, mas tem um detalhe que muita gente não considera. Ele funciona bem até uns milhares de números num papel, mas em escala maior o custo de memória começa a pesar. Se você for implementar isso num script, usar um array booleano de tamanho fixo é mais rápido do que ficar testando divisão a cada número com operador módulo, especialmente se o loop rodar milhões de vezes. Em Python, por exemplo, uma implementação ingênua com laço duplo leva cerca de 3 a 4 segundos pra 10 mil, enquanto o crivo fecha em menos de 0,05 segundos no mesmo hardware. A diferença é brutal.

Números primos de 0 a 100

Aplicando o crivo passo a passo, os números primos de 0 a 100 são exatamente esses: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97. São 25 no total. Se você fizer a contagem e aparecer 26, revisou algum múltiplo errado ou esqueceu de excluir o 1. Isso acontece com frequência. Tem dois pontos que eu aprendi na marra e que raramente aparecem em materiais introdutórios. O primeiro é que o 2 é o único primo par. Todo mundo esquece disso na primeira vez que tenta otimizar um filtro removendo os pares, e aí o 2some. Eu já perdi uma manhã inteira caçando bug numa função que suprimia todos os números divisíveis por 2, achando que o problema era no teste de unidade. O segundo ponto é sobre o 9. Parece primo à primeira vista porque só é divisível por 3 e por si mesmo, mas ele é composto. Quando você aplica o crivo corretamente, o 9 é riscado na passagem do 3. Em testes manuais, é um dos números que mais engana. Outro detalhe prático: não adianta testar divisibilidade por todos os números até 99. Só precisa verificar divisores até a raiz quadrada do número. Para o 97, por exemplo, basta testar divisores até 9,8. Isso reduz o trabalho experimental de forma significativa. Em uma verificação brut force, um número como 97 seria testado contra 96 divisores em média. Com o limite da raiz quadrada, cai para 9 testes. A economia é clara e se acumula conforme a faixa sobe.

Se a ideia é só consultar a lista de tempos em tempos, uma tabela simples ou até uma planilha resolve. Se precisa integrar em código, prefira um array pré-computado com os 25 valores já listados. Gerar via crivo em runtime funciona, mas reinventar a roda toda vez que o módulo carrega adiciona latência desnecessária, principalmente em serviços que rodam sob demanda. Em benchmarks rápidos, um lookup fixo é cerca de 200 vezes mais rápido do que executar o crivo a cada chamada em JavaScript no Node. Limitações existem. O crivo de Eratóstenes consome memória proporcional ao limite superior. Para faixas maiores que 100 milhões, o uso de bitmap ou um crivo segmentado se torna necessário. Não tente usar array de bools normais pra isso. E cuidado com falsos positivos em implementações apressadas. Um erro comum é iniciar o risco dos múltiplos a partir do próprio primo, o que não quebra o resultado, mas deixa o código menos limpo. O certo é começar a partir do quadrado do primo, que é onde os múltiplos menores já foram cobertos por primos anteriores.