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.

 

  1. Escolha o número de colunas e o número de linhas a considerar.
  2. Poderá desactivar a opção Som (que por defeito está activa).
  3. 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.