O crivo de Eratóstenes

Κόσκινον Ἐρατοσθένους Cribrum Eratosthenis Nicom. Ar. 1.13.2 c. AD 100

O crivo de Eratóstenes é um método usado pelos antigos matemáticos para isolar números primos[1].

A criação é atribuída tradicionalmente a Eratóstenes (-285/-194), terceiro bibliotecário da Biblioteca de Alexandria e um dos grandes sábios da Antiguidade. Um pouco modificado, o crivo continua sendo uma ferramenta muito útil nas pesquisas sobre a teoria dos números.

O sistema de Eratóstenes não foi encontrado em nenhum dos seus fragmentos conhecidos. Conhecemos o “crivo” através do texto Introdução à Aritmética (Nicom. Ar. 1.13.2), do matemático Nicômaco (c. 60/120).

Método básico (ou, como se diz na atualidade, “algorritmo”):

  1. escrever uma sequência de números inteiros, desde o número 1 até o máximo valor desejado;
  2. cortar o número 1;
  3. cortar todos os múltiplos de 2, exceto o 2 (é o primeiro número primo);
  4. o primeiro número não cortado é o segundo número primo (neste caso, o número 3);
  5. cortar todos os múltiplos de 3, maiores do que 3;
  6. repetir os passos acima para o número 5 e assim sucessivamente.
veja
links externos

Numa lista de números de 1 a 30, por exemplo, restarão os números 2 3 5 7 11 13 17 19 23 29.

Atualmente, há várias maneiras de implementar esse algorritmo em computador.

Eis um dos exemplos da Wikipedia que ilustra como isolar números primos até 120, implementado em gif “animado”:

f0051
Fig. 0051. O crivo de Eratóstenes.