Crivo de Eratóstenes

O Crivo de Eratóstenes é um antigo algoritmo usado para encontrar todos os números primos até um número inteiro dado. Ele foi desenvolvido pelo matemático grego Eratóstenes de Cirene por volta de 240 a.C. e é uma das maneiras mais eficazes de encontrar números primos em um intervalo específico.

O processo básico do Crivo de Eratóstenes é o seguinte:

1. Crie uma lista de números inteiros de 2 até o número limite que você deseja examinar em busca de números primos.

2. Comece com o primeiro número na lista (2) e marque-o como primo.

3. Em seguida, elimine todos os múltiplos desse número da lista, pois eles não podem ser primos. Por exemplo, se começamos com 2, eliminamos todos os múltiplos de 2 (4, 6, 8, etc.).

4. Avance para o próximo número não marcado na lista (neste caso, 3) e repita o processo, marcando-o como primo e eliminando seus múltiplos.

5. Continue esse processo até chegar ao final da lista.

6. Os números que restarem na lista após o processo são todos números primos.

O Crivo de Eratóstenes é eficaz porque elimina números compostos rapidamente, deixando apenas os números primos na lista. Ele é usado para gerar uma lista de números primos em um intervalo específico, o que é útil em várias aplicações matemáticas e computacionais, como criptografia e teoria dos números.