ATRACTOR

Vejamos, em detalhe, em que consiste o Crivo de Eratóstenes, usado para dar uma lista dos números primos menores ou iguais a um certo número.

Partimos de uma tabela, com um certo número de linhas e um certo número de colunas, contendo os números naturais desde \(1\) até ao número correspondente ao produto do número de linhas pelo número de colunas.

O primeiro passo é marcar o número \(1\) como não primo (pois, por definição, \(1\) não é primo). De seguida, marca-se, como primo, o primeiro número da tabela ainda não marcado (neste caso o número \(2\)) e marcam-se todos os seus múltiplos como não primos. Volta-se a marcar, como primo, o primeiro número da tabela ainda não marcado (nem como primo, nem como não primo) e marcam-se, como não primos, todos os seus múltiplos, que ainda não estejam marcados.

Repete-se este processo até que se chega a uma situação em que, ao marcar como primo o primeiro número da tabela ainda não marcado (nem como primo, nem como não primo), se verifica que todos os seus múltiplos na tabela já foram marcados previamente como não primos. Porquê? Qual é o primeiro múltiplo de um primo, diferente dele, que não está já marcado como não primo? É necessariamente o produto desse primo por si próprio. Então a situação referida ocorre para o primeiro primo tal que o produto dele por si próprio (o quadrado do primo) já não está na tabela. Nesse caso o primeiro número, diferente de si mesmo, que o admite como menor divisor (diferente de um) não está na tabela e, como tal, todos os números da tabela que sejam compostos admitem um divisor primo inferior a este número e, portanto, já tinham sido marcados como não primos. Por exemplo, na tabela \(10\) por \(5\), \(7 \times 7\) ainda está na tabela mas \(11 \times 11\) já não, por isso todos os múltiplos de \(11\) da tabela já foram previamente marcados como não primos. Na tabela de \(15\) por \(10\), \(11 \times 11\) ainda está na tabela, mas \(13 \times 13\) já não está. Quando se chega à situação descrita, todos os números ainda não marcados são primos.

Vejamos agora porque é que este método fornece, de facto, todos os números primos não superiores ao maior número que surge na tabela. Em primeiro lugar, todos os números marcados como não primos o são de facto: o primeiro número marcado como não primo foi o um (que não é primo, pois admite apenas um divisor); todos os outros números marcados como não primos são múltiplos de um número que no passo anterior foi marcado como primo (pelo que, sendo múltiplos desse número, o admitem como divisor, além de naturalmente também admitirem como divisores o um e o próprio número, sendo, portanto, números compostos).

E como garantir que o primeiro número ainda não marcado é sempre primo? Se ele for o primeiro número ainda não marcado, isso significa que não é múltiplo de nenhum número inferior a ele (excepto do número um), logo não admite nenhum divisor distinto de um e do próprio número, sendo portanto primo.

Note-se que depois do número \(3\) ser marcado como primo, marcam-se como não primos todos os seus múltiplos; o primeiro número que será marcado como não primo será o \(9\) \((3 \times 3)\). Assim, depois de marcar como não primos todos os múltiplos de \(3\), já podemos garantir que todos os números não marcados inferiores a \(9\) são primos, o que inclui, para além do número \(5\), o número \(7\).

Da mesma forma, depois do número \(5\) ser marcado como primo, o primeiro número que será marcado como não primo será o primeiro número que admite \(5\) como menor divisor, que é o \(25\) \((5 \times 5)\), logo todos os números ainda não marcados inferiores a \(25\) são primos, o que inclui para além do \(7\), os números \(11, 13, 17, 19\) e \(23\).

Portanto, até podemos garantir que não só o primeiro número ainda não marcado é primo, mas que todos os números ainda não marcados e que são menores que o seu quadrado são primos.