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óstenesPaul 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 ((circa?) 275-194 a.C.),Morris Klein, Mathematics for The Nonmathematician, Dover Publications, New York, 1967, p. 136:"Eratosthenes (275—194 B.C.)"<ref>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."</ref> o terceiro bibliotecário-chefe da Biblioteca de Alexandria desde 247.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.)")
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.
Visualização do Crivo center|Animação do crivo|frame|260x260px
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.Sieve of Eratosthenes - Benchmarks, site www.keil.com Uma das versões mais populares deste benchmark'' foi publicada na Revista Byte, no início dos anos 1980.The Sieve, Factoring and Primes, site home.hccnet.nlCódigo fonte do programa sieve.c, site www.cs.nthu.edu.tw
Ver também Crivo de Atkin
Categoria:Algoritmos matemáticos Categoria:Teoria dos crivos Categoria:Testes de primalidade