Crivo de Eratóstenes

Vamos agora encontrar todos os números primos menores do que 50 recorrendo a um método famoso.

O método que eu te proponho chama-se  “Crivo de Eratóstenes”em homenagem a Eratóstenes que além de matemático, foi poeta, historiador e geógrafo, elaborou uma lista de números primos conhecida por este nome. O método consiste em começar por escrever todos os números naturais de 2 até 50 (o número um já foi eliminado desta lista, pois como sabes este número não é primo). Seguidamente, começamos por eliminar os múltiplos de dois superiores a dois, a seguir, os múltiplos de três superiores a três e assim sucessivamente, ou seja, removemos todos os múltiplos de primos não superiores a raíz quadrada de 50 ( os números superiores a este que não são primos já estão todos sublinhados). Deste modo, todos os números de 2 a 50 excepto os números primos serão removidos. Ficamos assim com a lista dos números primos inferiores a 50. No quadro que se segue está explicado o método:

Primeiro sublinhamos todos os números maiores do que dois múltiplos de dois. Seguidamente, sublinhamos todos os números superiores a três múltiplos de três. Note-se que os múltiplos comuns de dois e de três estão duplamente sublinhados. Depois, foram sublinhados todos os números maiores do que cinco que são múltiplos de cinco (passamos de três para cinco, visto que o quatro já foi sublinhado, logo não é primo e o objectivo é encontrar todos os números não sublinhados, ou seja que tenham apenas dois divisores e portanto sejam primos). Novamente, verificamos que há números sublinhados mais do que uma vez, desta vez teremos números sublinhados três vezes que são os múltiplos comuns de dois, três e cinco. O número que se segue, é o sete, visto que o seis já está sublinhado pois é múltiplo de dois e de três. O processo termina aqui, visto que qualquer número superior a sete é maior do que a raíz quadrada de 50.  Os números sublinhados deverão ser todos eliminados. Obtemos deste modo a seguinte lista, constituída pelos números primos menores do que 50:

2   3   5   7   11   13   17   19   23  29  31   37   41   43   47

Os números compostos foram todos eliminados por este processo.