Aritmética · Algoritmos · Números Primos
Crivo de Eratóstenes
O algoritmo mais elegante da Antiguidade para encontrar todos os primos até um limite — com mais de 2200 anos de uso.
Para cada primo p encontrado: riscar todos os múltiplos de p
Repetir até p > √N — os não riscados são primos
Como funciona o Crivo
O Crivo de Eratóstenes encontra todos os primos até N de forma sistemática:
- Listar todos os inteiros de 2 a N (começamos de 2 pois 1 não é primo por definição).
- O primeiro número não riscado é 2 — é primo. Riscar todos os múltiplos de 2: 4, 6, 8, 10, …
- O próximo não riscado é 3 — é primo. Riscar todos os múltiplos de 3: 9, 12, 15, … (6 já foi riscado).
- O próximo não riscado é 5 — é primo. Riscar múltiplos de 5. Continuar com 7, 11, 13, …
- Parar quando p > √N. Qualquer número composto maior que √N já foi riscado por algum fator menor. Os sobreviventes são todos primos.
Para cada primo p, podemos começar a riscar de p² (não de 2p), pois todos os múltiplos menores de p² já foram riscados por primos anteriores. Isso reduz o trabalho consideravelmente.
Por que o algoritmo está correto
A chave é o Teorema Fundamental da Aritmética (que já estudamos): todo número composto tem um fator primo menor ou igual à sua raiz quadrada.
Seja n composto. Então n = a·b com 1 < a ≤ b < n. Como a·b = n, temos a ≤ √n. Portanto n tem um fator primo p ≤ a ≤ √n. Logo quando o crivo chega ao passo p, n já terá sido riscado como múltiplo de p.
Conclusão: ao terminar o crivo, tudo que não foi riscado não tem nenhum fator primo ≤ √N — portanto é primo. ∎
O Crivo de Eratóstenes básico tem complexidade O(N·log(log N)) — quase linear! É muito eficiente para N até alguns bilhões com versões otimizadas (Crivo Segmentado).
Crivo em Ação
Clique em "Executar Crivo" para ver o algoritmo eliminar os compostos um a um, revelando os primos até 150.
Distribuição dos Primos e Variantes
O Teorema dos Números Primos (Hadamard e de la Vallée-Poussin, 1896) diz que o número de primos até N, denotado π(N), satisfaz:
Exemplos: π(100) = 25 (há 25 primos até 100) · π(1000) = 168 · π(10⁶) = 78.498. Os primos ficam cada vez mais esparsos, mas nunca cessam.
| N | π(N) — primos até N | N/ln N (aprox.) |
|---|---|---|
| 100 | 25 | 21,7 |
| 1.000 | 168 | 144,8 |
| 10.000 | 1.229 | 1.085,7 |
| 100.000 | 9.592 | 8.685,9 |
| 1.000.000 | 78.498 | 72.382,4 |
Crivo de Sundaram — encontra primos da forma 2k+1. Crivo Segmentado — divide [1,N] em segmentos para funcionar com pouca memória. Crivo de Atkin — O(N/log log N), ligeiramente mais rápido para N muito grande.