Em que consiste o Crivo de Eratóstenes?
O Crivo de Eratóstenes é um método para determinar todos os números primos menores ou iguais a um certo número.
A palavra "crivo" refere-se a um utensílio que serve para separar diferentes componentes de uma mistura, retendo as substâncias maiores e deixando passar as substâncias de dimensões mais reduzidas.
Mas será que, ao aplicar o Crivo de Eratóstenes, temos como objectivo separar diferentes componentes que estão misturadas? De certa forma, sim... Usando o Crivo de Eratóstenes iremos separar os números primos dos números não primos (ou seja, do número um e dos números compostos).
Na aplicação interactiva seguinte poderá aplicar este método para determinar todos os números primos não superiores a um dado valor. Tente seguir os passos indicados na aplicação.
- Escolha o número de colunas e o número de linhas a considerar.
- Poderá desactivar a opção Som (que por defeito está activa).
- Depois destas configurações iniciais, basta seguir as instruções dadas em cada momento na aplicação. Quando terminar, surgirá um botão "Recomeçar". Se clicar neste botão, é-lhe permitido escolher novamente o número de colunas e de linhas e voltar a iniciar todo o processo.
Procure seguir os passos da aplicação sem ver o que se segue. Se algum dos passos da aplicação não foi claro, consulte aqui algumas explicações sobre o método usado na procura de números primos e a justificação desse mesmo método.
Notemos que este método é bastante prático para determinar todos os números primos inferiores a um certo valor, porque envolve apenas multiplicações (na esolha dos múltiplos de um primo) e, em geral, parece-nos mais fácil multiplicar do que dividir.
Contudo, note-se que dado qualquer número natural, para testar se ele é primo não é necessário aplicar o crivo de Eratóstenes; basta verificar se é divisível por algum número primo \(p\) cujo produto \(p\times p\) não exceda o número dado.
Antes de ver a justificação que se segue pense no porquê desta afirmação.
Como vimos na questão II, o primeiro número composto que admite um número primo \(p\) como o seu menor divisor (distinto de \(1\)) é \(p \times p\). Dito de outra forma, qualquer número composto inferior a \(p \times p\) terá de admitir como divisor um número primo inferior a \(p\).
Assim, podemos concluir que, dado um número natural superior a \(1\), se ele não for divisível por nenhum primo \(p\) tal que \(p \times p\) seja menor ou igual ao número dado, então o número dado é primo.
