Crivo de Eratóstenes

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

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
Animação do crivo

Utilização em linguagens de programação

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]

Ver também

Referências
  1. 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. 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
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.