|
|
|
|
|
O CRIVO DE ERATÓSTENES |
|
|
|
Eratóstenes viveu no século III a.C, em uma colônia grega na Líbia chamada Cyrene. |
|
|
|
Dentre suas contribuições, destaca-se um método para a determinação de números primos, o qual é conhecido como o crivo de Eratóstenes. |
|
|
|
Por exemplo, para determinar os números primos menores que 100, o primeiro passo é listar, em ordem crescente, todos os números naturais de 2 até 100. |
|
|
|
Em seguida, retiramos todos os números maiores que 2 e múltiplos de 2 (4, 6, 8, ...), os quais não são primos, porque são números pares. |
|
|
|
Os próximos números a serem retirados são os múltiplos de 3 maiores que 3 (9,15,21,..); os quais também não são primos, pois são divisíveis por 3. |
|
|
|
Continuando, retiramos os múltiplos de 5 maiores que 5 e, finalmente, os múltiplos de 7 maiores que 7. |
|
|
|
Os números que restarem são todos os números primos menores do que 100, isto é, |
|
|
|
|
|
Observe, que não é necessário retirar os múltiplos de 11, uma vez que que o primeiro múltiplo de 11 a ser retirado seria o número 11.11 = 121, o qual é maior que 100. |
|
|
|
Logo, quando utilizamos o crivo de Eratóstenes para encontrar todos os números primos menores que um número natural n, é suficiente retiramos apenas os números múltiplos dos primos menores que a raiz quadrada de n. |
|
|
|
|
|
|
|
|
