O crivo de Eratóstenes

Neste post vou voltar a tratar de um dos meus assuntos preferidos (como muitos já devem ter percebido), números primos. Caso o nome "Eratóstenes" lhe pareça familiar, é porque já falamos dele em outro post, tratando de como medir a curvatura da Terra (aqui e aqui).

O crivo de Eratóstenes é, basicamente, um algoritmo para achar números primos. Mas antes de comentá-lo, é melhor você ver como ele funciona.

Problema: Como listar todos os números primos até um determinado número (por exemplo, até 25).

Só para relembrar, número primo é todo número maior que 1 que só pode ser dividido (divisão exata) por 1 e por ele mesmo. Ao contrário do que diz a crença popular - como diria meu professor - , o número 1 não é primo, "um é um".

Para resolver o problema acima, você poderia simplesmente ir de número em número, testando se ele é primo, até chegar no limite desejado, no caso, 25. Mas esta não é uma estratégia muito inteligente. Abordaremos o problema usando o Crivo de Eratóstenes.

Mas... o que é um crivo?

Antes de mais nada, é bom esclarecer o que é um crivo. Dentre outros significados, crivo pode ser entendido como uma peneira. Isto faz sentido pois este algoritmo age como se estivéssemos peneirando (com uma peneira de primos) os números para que sobrem apenas os que queremos, isto é, os número primos.

E como funciona esse tal de crivo?

Primeiro, listamos todos os números de 0 até o número que queremos, no caso, 25. Na verdade, poderíamos começar do 2 pois este é o primeiro primo sempre.

Agora riscamos o 0 e o 1 pois já sabemos que não são primos. Depois, pegamos o primeiro primo de nossa lista, ou seja: 2, e excluímos todos os seus múltiplos (menos o próprio número). Ou seja, "riscamos" todos os pares a partir de 4.

Agora, pegamos o próximo primo da lista, 3. E repetimos o processo, excluindo todos os seus múltiplos.
Perceberam a ideia? Como queremos deixar apenas os números primos, excluímos todos os números que são múltiplos de algum outro primo, pois, com certeza, estes não serão primos.

Baseado nisso, rapidamente poderíamos apontar alguns pontos fracos e alguns pontos a favor desse algoritmo.
Um ponto a favor é este processo de "riscar os múltiplos" é bem simples de se fazer, pois é só "ir pulando e riscando" (por exemplo) de 3 em 3 - no caso em que estamos "crivando" o primo 3.
Um ponto fraco imediato é que temos que listar muitos números e isso dá trabalho. Outra coisa que você poderia se questionar é: "Espera aí! Tudo bem que a gente poupa algum esforço eliminando os múltiplos de determinados primos, mas ainda assim, temos que testar muitos números para sabermos se são primos ou não.

Quando a gente para de "crivar"?

Eratóstenes mostrou que podemos parar de riscar múltiplos quando chegamos na raiz quadrada do número máximo que estipulamos (no nosso caso, o número 25). E isso reduz muito o nosso esforço!

Isto decorre do fato de que o menor primo que divide um número nunca pode ser maior que a raiz quadrada desse número. Vale lembrar que o Rodrigo provou esta afirmação no post Um algoritmo simples para teste de primalidade, confiram lá.

Portanto, parece razoável parar de "crivar" na raiz do número máximo, pois, se depois de termos "crivado" até a raiz do número máximo, sobrasse algum número composto (isto é, um número maior que um que não é primo) depois da raiz do número máximo, ele teria algum fator primo menor que sua própria raiz, o que é absurdo pois todos os primos menores que sua raiz já tinham sido "crivados".

Voltando ao problema...

Tendo esta ferramenta em mãos, vamos terminar de listar os nossos primos. Temos que parar na raiz quadrada de 25 [1].


Portanto, bastar "crivarmos" o 5, e teremos terminado.

E estes são todos os primos até 25!

Implementando este algoritmo no computador

Ok, o algoritmo é genial, mas parece muito pouco prático, quem tem paciência de ficar escrevendo tudo no papel e depois ir riscando um a um os números? Bem, os gregos tinham, mas a gente não precisa ter.

Segue abaixo um exemplo de como podemos implementar um algoritmo desse tipo no computador. "//" denota comentário




















Clique na imagem para ampliar.

Se você leu com cuidado o meu algoritmo, pode ter percebido algumas falhas óbvias, como o excessivo uso de memória. Meu intuito com ele não era realizar nada otimizado, e sim fazê-lo da maneira mais natural e didática possível. Com ele, consegui listar rapidamente (cerca de um minuto) todos os primos até 10 milhões. No artigo da Wikipedia, linkado mais abaixo, temos outros exemplos de algoritmos.

Fico por aqui, até.

Notas:

[1] Quando o número máximo que estipulamos não é um quadrado perfeito (o que irá acontecer na maioria das vezes), basta aproximarmos seu quadrado para o inteiro logo abaixo.

Leia também o artigo na Wikipedia!