Numeros Primos 1 100

Como listar e usar numeros primos de 1 a 100

Os números primos até cem são vinte e cinco números no total. A lista é fixa, não muda, e quem precisa consultá-la com frequência costuma já decorá-la de cor. Para quem está aprendendo, o processo é mais lento. A primeira coisa que a maioria das pessoas faz é tentar dividir cada número por todos os anteriores, o que é desnecessário. O crivo de Eratóstenes resolve isso em segundos.

Definição técnica e aplicação prática

Um número primo é inteiro maior que um e divisível apenas por um e por ele mesmo. O dois é o único par. A partir daí, todo primo é ímpar, mas nem todo ímpar é primo. Esse detalhe causa confusão constante quando alguém tenta programar uma verificação sem entender o fundamento.

Lista completa de numeros primos 1 100

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. O trinta e nove é divisível por três e treze. O cinquenta e um é divisível por três e dezessete. O sessenta e é divisível por três. A armadilha é olhar para o último dígito e achar que a coisa acabou. Não acabou.

Método passo a passo para gerar a lista

Você escreve os números de dois a cem em uma linha. O dois é primo. Você risca todos os seus múltiplos, quatro, seis, oito, e assim por diante. O próximo número não riscado é o três. Risca-se todos os múltiplos dele. Depois o cinco, depois o sete. Como 7 multiplicado por 7 é 49 e o próximo fator seria 11, que já foi processado indiretamente, você para quando o quadrado do número atual ultrapassar cem. Isso corta o trabalho pela metade em relação ao método ingênuo de testar divisibilidade um por um. A complexidade desse algoritmo é O(n log log n), o que significa que even para limites muito maiores que cem o crivo ainda é rápido o suficiente para uso prático em aplicações que precisam de primos abundantes. Para gerar apenas uma verificação pontual de um número, a divisão testada até a raiz quadrada é mais eficiente em memória, mas lenta em CPU se você precisar verificar milhares de valores.

Problema real que encontrei

Em um projeto de criptografia didática, precisei gerar listas de primos em um ambiente embarcado com memória extremamente limitada, menos de dois kilobytes disponíveis para toda a lógica. O crivo clássico falhou porque exigiria um array de bits de cem posições mais lógica de traversal. A solução que funcionou foi um gerador sob demanda que testava divisibilidade apenas por primos já encontrados até a raiz quadrada do número em análise. Para o limite de cem, esse approach ocupava cerca de oitenta bytes de estado. Para limites maiores, como dez milhões, mudei para o crivo segmentado, que divide o intervalo em blocos que cabem na cache do processador.

Pegadinhas que ninguém ensina

O número um não é primo. Muita gente esquece e coloca ele na lista, o que quebra teoremas inteiros depois. O primo dois é o único par. A partir dali, todos os primos terminam em 1, 3, 7 ou 9. Isso permite filtragem rápida antes de qualquer teste de divisibilidade. Em português, o termo correto é primo, não primo número. A gramática pede concordância direta. Um erro comum em implementações é começar o crivo a partir do um em vez do dois. Isso gera um vazio lógico porque o algoritmo assume que um é primo e marca todos os números como não primos, já que um divide tudo. O resultado é uma lista vazia ou completamente errada. O dois precisa sempre ser tratado como caso base.

Limitações conhecidas

O crivo de Eratóstenes consome memória linear em relação ao limite superior. Para cem é irrelevante, mas para bilhões isso se torna proibitivo. Nessas situações, testadores de primalidade probabilísticos como Miller-Rabin são a alternativa padrão. Eles não geram listas completas, apenas verificam se um número específico é primo com uma margem de erro ajustável. Para listas, o crivo segmentado ou o crivo de Atkins são melhores opções, embora Atkins tenha overhead constante maior e só vire a vantagem em limites acima de cem milhões. Nenhum desses métodos é perfeito. Se você precisa de todos os primos até um limite fixo pequeno como cem, a lista já conhecida é mais rápida que qualquer geração. Se o limite é desconhecido ou enorme, o caminho muda completamente. Escolha a ferramenta baseada no problema real, não no que soa mais elegante num livro texto.