O que é Crivo de Eratóstenes
O Crivo de Eratóstenes é um método muito simples e prático utilizado para encontrar números primos até um determinado número inteiro, sendo o primeiro teste de primalidade conhecido. A criação deste método é atribuída ao matemático grego Eratóstenes (285 a.C – 194 a.C), terceiro bibliotecário-chefe da Biblioteca de Alexandria. Mais tarde foram desenvolvidos outros testes de primalidade, entre os quais os trabalhos do teólogo e matemático francês Marin Mersenne (1588-1648), autor da célebre fórmula dos números de Mersenne (2p-1, em que p é número primo) que permite verificar se determinado número é ou não primo.
Exemplo de funcionamento do Crivo de Eratóstenes:
- O primeiro passo é escolher o maior número inteiro a ser verificado. Neste exemplo será considerado o número 50.
- Segue a determinação do maior número a ser estudado – este número corresponderá à raiz quadra do valor limite arredondado para baixo. Neste caso, a raiz de 50 arredondada para baixo é 7.
- Cria-se de seguida uma lista onde deverão ser colocados todos os números inteiros desde o número 2 até ao valor limite, neste caso o número 50.
- O passo seguinte é identificar o primeiro número primo da lista, isto é o número 2, e retirar todos os seus múltiplos; neste caso ficarão o número 2 e todos os números ímpares que se lhe seguem, até 49.
- Faz-se o mesmo para o número seguinte da lista (o número 3), retirando todos os seus múltiplos da lista; após este passo, restarão na lista os números 2, 3 e todos os números ímpares que não sejam múltiplos de 3.
- O número seguinte da lista é 0 5, devendo executar-se o mesmo processo. Por fim, resta aplicar o mesmo processo ao número 7 (maior número a ser estudado conforme determinado antes).
- Após a aplicação deste processo, restarão na lista os números 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43 e 47. São estes os números primos inferiores a 50.
271 Visualizações 1 Total
