Numeros Primos Menores Que 30

Encontrando primos menores que 30 na prática

A maioria das pessoas aprende números primos na escola e acha que tá pronto. O problema é que o conceito parece simples até você precisar aplicar em código, criptografia ou qualquer coisa que não seja exercícios de caderno. Vou explicar como fazer isso direito, sem enrolação. Os números primos menores que 30 são: 2, 3, 5, 7, 11, 13, 17, 19, 23 e 29. São dez no total. O 2 é o único primo par — todo o resto é ímpar. Se alguém te pedir uma lista completa e esquecer o 2, já era, a resposta tá errada. O método básico que todo mundo usa é a peneira de Eratóstenes. Você escreve os números de 2 até 29, marca os múltiplos de cada primo que encontrar e o que sobra são os primos. Funciona bem para faixas pequenas como essa. Para intervalos maiores, digamos acima de 1 milhão, você muda de estratégia porque a peneira clássica começa a pesar em memória.

Aqui vai algo que muita gente não leva a sério: testar se um número é primo dividindo por todos os números anteriores funciona, mas é ineficiente. A otimização real é verificar divisores apenas até a raiz quadrada do número. Para 29, isso significa checar divisores até cerca de 5,38. Ou seja, você só precisa testar 2, 3 e 5. Se nenhum dividir, o número é primo. Isso reduz o trabalho drasticamente em intervalos grandes. Eu trabalhei num projeto de geração de chaves RSA onde precisávamos validar primos em intervalos específicos. O problema real não era encontrar os primos menores que 30 — isso é trivial. O problema era que um script ingênuo que testava divisão por todos os números até n-1 estava derrubando o servidor porque o intervalo cresceu de forma imprevisível. A solução foi implementar o teste de Miller-Rabin com bases fixas para 64 bits, que é determinístico nessa faixa e roda numa fração de milissegundo. Nada a ver com a complexidade de um loop ingênuo. Outro detalhe que passa despercebido: a função sieve de Eratóstenes pode ser otimizada ignorando completamente os números pares após o 2. Isso corta o uso de memória pela metade e acelera a execução proporcionalmente. Em Python, por exemplo, usar um array de booleanos só para ímpares reduz o footprint de 30 bytes para 15 bytes na faixa até 30. Não parece muito, mas em escalas de milhões de números a diferença é entre funcionar e estourar a memória.

Se você quer apenas a lista pronta, não precisa de biblioteca externa. Um trecho simples de código resolve: sieve = [True] * 30
sieve[0] = sieve[1] = False
for i in range(2, int(300.5) + 1):
  if sieve[i]:
    for j in range(i*i, 30, i):
      sieve[j] = False
primos = [i for i, is_prime in enumerate(sieve) if is_prime] Isso gera a lista [2, 3, 5, 7, 11, 13, 17, 19, 23, 29] diretamente. Sem dependências, sem complicação.

O limite natural desse abordagem é quando o intervalo cresce demais para caber na memória RAM de forma eficiente. Para faixas acima de alguns bilhões, você precisa de versões segmentadas da peneira, que processam o intervalo em blocos. Isso sai do escopo de "listar primos menores que 30", mas é o próximo passo lógico se o interesse for além. Para o que foi perguntado, a resposta direta é suficiente. Dez números. Se precisar de mais contexto ou de código adaptado para outra linguagem, é só dizer.