Entre 0 E 30 Quantos Números Primos É Possível Identificar

Contagem de primos no intervalo fechado [0, 30]

Vou direto ao ponto. Entre 0 e 30 existem 10 números primos: 2, 3, 5, 7, 11, 13, 17, 19, 23 e 29. Acho que a pergunta mais interessante aqui não é o resultado final, mas como chegar até ele de forma confiável. Muita gente erra na hora de definir os limites do intervalo — se o "entre" inclui ou não os extremos, por exemplo. No caso, 0 e 30 não são primos de qualquer jeito, então faz pouca diferença prática, mas em intervalos maiores isso pode mudar o resultado.

entre 0 e 30 quantos números primos é possível identificar

A resposta prática é 10. Mas quero mostrar o método porque quando você sobe para intervalos como 0 a 10.000, não dá pra confiar na cabeça. O crivo de Eratóstenes é o método que eu uso na prática. Você pega uma lista de números, marca o 2 como primo e riscas todos os seus múltiplos. Depois avança para o próximo não-riscado (3), riscas os múltiplos dele, e repete até a raiz quadrada do limite superior. Para 30, você para em 5, porque raiz quadrada de 30 é cerca de 5,47. A partir daí, o que sobrar não-riscado são os primos. Eu já perdi tempo testando divisões individuais em intervalos maiores porque alguém sugeriu que o crivo era "gasto computacionalmente". Em Python, rodar um crivo até 30 leva menos de 0,1 milissegundo. Até 1 milhão, fica em torno de 30 milissegundos num hardware razoável. O teste de divisibilidade pura é muito mais lento quando o número sobe.

Um detalhe que muita gente esquece: o número 1 não é primo. É o erro mais comum que vejo em listas geradas automaticamente. Se o seu código marca 1 como primo, o resultado tá errado desde o início. O 2 é o único primo par — a partir daí, só ímpares podem ser primos, então já dá pra pular a verificação dos pares em qualquer implementação prática. Outro ponto que passa despercebido: a densidade dos primos diminui conforme o número cresce. Entre 0 e 30, a taxa é de 33% (10 em 30). Entre 0 e 1.000, cai para cerca de 17%. Entre 0 e 10 milhões, cerca de 6%. Se você precisa contar primos em intervalos grandes com frequência, vale a pena implementar um crivo pré-computado em vez de testar cada número individualmente.