Crivo de Eratóstenes

Origem: Wikipédia, a enciclopédia livre.
Saltar para a navegação Saltar para a pesquisa

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 (a.c. 285-194 a.C.), o terceiro bibliotecário-chefe da Biblioteca de Alexandria.

Explicação do algoritmo[editar | editar código-fonte]

Question book.svg
Esta seção não cita fontes confiáveis e independentes, o que compromete sua credibilidade (desde novembro de 2017). Por favor, adicione referências e insira-as corretamente no texto ou no rodapé. Conteúdo sem fontes poderá ser removido.
Encontre fontes: Google (notícias, livros e acadêmico)

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

  • Inicialmente, determina-se o maior número a ser checado. 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: 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, e 30.
  • Encontre o primeiro número da lista. Ele é um número primo, 2.
  • Remova da lista todos os múltiplos de 2 até 30. No nosso exemplo, a lista fica: 2, 3, 5, 7, 11, 13, 15, 17, 19, 23 e 29.
  • O próximo número da lista é 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[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.[1] Uma das versões mais populares deste benchmark foi publicada na Revista Byte, no início dos anos 1980.[2][3]

Ver também[editar | editar código-fonte]

Referências

  1. Sieve of Eratosthenes - Benchmarks, site www.keil.com
  2. The Sieve, Factoring and Primes, site home.hccnet.nl
  3. Código fonte do programa sieve.c, site www.cs.nthu.edu.tw