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 (c. 285-194 a.C.), o terceiro bibliotecário-chefe da Biblioteca de Alexandria.
Índice |
[editar] 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 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 30.
- Encontre o primeiro número da lista. Ele é um número primo, 2.
- Remova da lista todos os múltiplos do número primo encontrado. No nosso exemplo, a lista fica: 2 3 5 7 9 11 13 15 17 19 21 23 25 27 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 29. O próximo número, 5, também é primo; a lista fica: 2 3 5 7 11 13 17 19 23 29. 5 é o último número a ser verificado, conforme determinado inicialmente. Assim, a lista encontrada contém somente números primos.
[editar] Visualização do Crivo
[editar] 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.[1] Uma das versões mais populares deste benchmark foi publicado na Revista Byte, no início dos anos 1980.[2][3]
[editar] Ver também
Referências
- ↑ Sieve of Eratosthenes - Benchmarks, site www.keil.com
- ↑ The Sieve, Factoring and Primes, site home.hccnet.nl
- ↑ Código fonte do programa sieve.c, site www.cs.nthu.edu.tw
