O quê é o Crivo de Eratóstenes?
O Crivo de Eratóstenes é um método antigo e simples para encontrar todos os números primos menores que um determinado número natural. Esse método foi desenvolvido pelo matemático grego Eratóstenes de Cirene por volta do século III a.C. O algoritmo funciona de forma iterativamente removendo todos os números compostos do intervalo.
Quais são as características do Crivo de Eratóstenes?
- O Crivo de Eratóstenes encontra todos os número primos em um intervalo.
- O Crivo de Eratóstenes é um algoritmo determinístico.
- O Crivo de Eratóstenes requer um espaço de memória auxiliar para funcionar.
Quais as aplicações do Crivo de Eratóstenes?
- Algoritmos de Criptografia - Alguns sistemas criptográficos modernos, como o RSA, dependem da dificuldade de fatorar números grandes em seus fatores primos. O Crivo de Eratóstenes pode ser usado para gerar uma lista de números primos que podem ser usados como base para a geração de chaves criptográficas.
- Algoritmos de Fatoração - Alguns algoritmos de fatoração, como o método da fatoração por tentativa, dependem da verificação de primalidade dos números para identificar seus fatores primos. O Crivo de Eratóstenes pode ser usado para gerar uma lista de números primos que podem ser usados para acelerar a fatoração desses números.
- Algoritmos de Geração de Números Aleatórios - Alguns algoritmos de geração de números aleatórios dependem da geração de números primos aleatórios. O Crivo de Eratóstenes pode ser usado para pré-computar uma lista de números primos e, em seguida, selecionar um número aleatório dessa lista para uso em algoritmos de geração de números aleatórios.
Quais são os passos do Crivo de Eratóstenes?
- Inicie com uma lista de números inteiros de 2 até o limite máximo desejado.
- Marque o número 2 como primo e circule-o na lista.
- Para cada número não marcado na lista, identifique-o como primo e circule-o, em seguida, marque todos os seus múltiplos como compostos (não primos) riscando-os da lista.
- Continue o processo até que todos os números na lista tenham sido marcados como primos ou compostos.
- A lista final conterá apenas os números primos menores que o limite máximo desejado.
Qual o desempenho do Crivo de Eratóstenes?
O desempenho do Crivo de Eratóstenes depende do limite máximo desejado para a lista de primos. O algoritmo tem complexidade de O(n log log n), onde n é o limite máximo desejado.
Como implementar o Crivo de Eratóstenes?
Veja o código completo no GitHub.