Saltar para o conteúdo

Crivo de Eratóstenes

Origem: Wikipédia, a enciclopédia livre.

O Crivo de Eratóstenes é um algoritmo e um método simples e prático para encontrar números primos até um certo valor limite. Segundo a tradição, foi criado pelo matemático grego Eratóstenes[1] ((circa?) 275-194 a.C.),[2][3] o terceiro bibliotecário-chefe da Biblioteca de Alexandria desde 247.[4]

Explicação do algoritmo

[editar | editar código-fonte]

Para exemplificá-lo, vamos determinar a lista de números entre 1 e 30.

  • Inicialmente, determina-se o maior número a ser verificado. Ele corresponde à raiz quadrada do valor limite, arredondado para baixo. No caso, a raiz de 30, arredondada para baixo, é 5.
  • Crie uma lista de todos os números inteiros de 2 até o valor limite, neste caso 30.
  • Encontre o primeiro número da lista. Ele é um número primo, 2.
  • Remova da lista todos os múltiplos de 2 (exceto ele próprio) até o valor limite. No nosso exemplo, a lista contem 2 e os números ímpares até 29.
  • O próximo número da lista após o primo anterior é primo. Repita o procedimento. No caso, o próximo número da lista é 3. Removendo seus múltiplos, a lista fica: 2, 3, 5, 7, 11, 13, 17, 19, 23, 25 e 29. O próximo número, 5, também é primo; a lista fica: 2, 3, 5, 7, 11, 13, 17, 19, 23 e 29. 5 é o último número a ser verificado, conforme determinado inicialmente. Assim, a lista encontrada contém somente números primos.[1][5]

Visualização do Crivo

[editar | editar código-fonte]
Animação do crivo

Utilização em linguagens de programação

[editar | editar código-fonte]

A simplicidade do código faz com que este seja usado como benchmark para comparar compiladores e chips.[5] Uma das versões mais populares deste benchmark foi publicada na Revista Byte, no início dos anos 1980.[6][7]

Referências

  1. a b Paul Hoffman, The Man Who Loved Only Numbers: The Story of Paul Erdős and the Search for Mathematical Truth, (New York: Hyperion), 1998, p. 35. ISBN 0-7868-6362-5
  2. Morris Klein, Mathematics for The Nonmathematician, Dover Publications, New York, 1967, p. 136:
    "Eratosthenes (275—194 B.C.)"
  3. The New Century Classical Handbook; Catherine Avery, redator; Appleton-Century-Crofts, New York, 1962, p. 447:
    "Eratosthenes... born... c275 B.C.; died c194 B.C."
  4. The New Century Classical Handbook; Catherine Avery, redator; Appleton-Century-Crofts, New York, 1962, p. 447:
    "Eratosthenes... the chief librarian (the third to hold the position) of the great Library at Alexandria (247 B.C.)"
    (""Eratóstenes... o bibliotecário-chefe (o terceiro a ocupar o cargo) da grande Biblioteca de Alexandria (247 a.C.)")
  5. a b Sieve of Eratosthenes - Benchmarks, site www.keil.com
  6. The Sieve, Factoring and Primes, site home.hccnet.nl
  7. Código fonte do programa sieve.c, site www.cs.nthu.edu.tw