O CRIVO DE ERATÓSTENES

Para encontrar todos os números primos numa lista de números inteiros pequenos, o modo mais rápido e fácil é o de Erastótenes. Tendo em conta que a multiplicação é uma operação mais fácil de realizar do que a divisão, Erastótenes de Cirene (no século III a.C.) teve a brilhante idéia de organizar estas computações em forma de crivo ou peneira.

Criando um crivo

Um dos meios mais eficientes de achar todos os números primos pequenos, por exemplo os menores do que 10.000.000, é usando o Crivo de Erastótenes (± 240 a.C.). Basta fazer uma lista com todos os inteiros maiores que um e menores ou iguais a n e riscar os múltiplos de todos os primos menores ou iguais à raiz quadrada de n (n^½). Os números que não forem riscados são os números primos.

A título de exemplo, vamos determinar os primos menores ou iguais a 20:

1. Inicialmente faz-se a lista dos inteiros de 2 a 20.

          2   3   4   5   6   7   8   9  10
     11  12  13  14  15  16  17  18  19  20

2. O primeiro número (2) é primo. Vamos mantê-lo e riscar todos os seus múltiplos. Desta forma, obtemos:

          2   3   4   5   6   7   8   9  10
     11  12  13  14  15  16  17  18  19  20

3. O próximo número "livre" é o 3, outro primo. Vamos mantê-lo e riscar seus múltiplos:

          2   3   4   5   6   7   8   9  10
     11  12  13  14  15  16  17  18  19  20

4. O próximo número primo é 5, porém não é necessário repetir o procedimento porque 5 é maior que a raiz quadrada de 20 (20^½ = 4,4721). Os números restantes são primos, destacados abaixo:

          2   3   4   5   6   7   8   9  10
     11  12  13  14  15  16  17  18  19  20

Os números primos encontrados foram {2, 3, 5, 7, 11, 13, 17, 19}.

A DIVISÃO POR TENTATIVA

Para determinar se um determinado número inteiro pequeno é primo, a divisão por tentativa funciona bem. Basta dividi-lo por todos os primos menores ou iguais à sua raiz quadrada.

Por exemplo, queremos saber se 323 é um número primo. A raiz quadrada de 323 é 323^½ = 17,9722, portanto, vamos dividir 323 por 2, 3, 5, 7, 11 e 17. Se nenhum destes primos dividir 323, então ele será primo:

     Divisão          Resto     Divide
    -----------------------------------
     323 ÷  2 = 161     1         Não
     323 ÷  3 = 107     2         Não
     323 ÷  5 =  64     3         Não
     323 ÷  7 =  46     1         Não
     323 ÷ 11 =  29     4         Não
     323 ÷ 13 =  24    11         Não
     323 ÷ 17 =  19     0         SIM

O inteiro 323 NÃO é primo porque é divisível por 17.

Se estivéssemos procurando por um número primo titânico, com mais de 10.000 algarismos, nunca poderíamos dividí-lo por todos os primos menores que a sua raiz quadrada. Ainda assim, mesmo nestes casos, a divisão por tentativa é utilizada para fazer um rastreamento inicial. Faz-se divisões com alguns milhares de primos pequenos e depois aplica-se um teste de primalidade.

No caso de n ter 25 dígitos ou mais, a divisão por tentativa usando primos menores que sua raiz quadrada é impraticável. Se n tiver 200 dígitos, então a divisão por tentativa é impossível.

ALGORITMOS

Existem alguns algoritmos bastante simples que podem ser usados para se testar a primalidade. Entre eles estão:

Divisões Sucessivas

O mais simples dos testes de primalidade consiste em dividir um número n por todos os números inteiros que estiverem na faixa que vai de 2 até n - 1. Se n for divisível por qualquer um deles, então n é um número composto. Caso contrário, é um número primo.

Simplificação das Divisões Sucessivas

Não há a necessidade das divisões serem efetuadas até n - 1. Sabe-se que, se o número que está sendo testado não for divisível por um inteiro entre 2 e a raiz quadrada de n (n^½), então n é um número primo. Caso contrário, é um número composto. A eficiência deste algoritmo é maior do que a do anterior devido à redução do número de divisões.

Divisões Sucessivas eliminando números pares

A eficiência do algoritmo pode ser muito aumentada se, com exceção do 2, todos os inteiros pares forem excluídos.

Usando uma característica dos inteiros

Um ganho de eficiência significativo pode ser obtido se levarmos em consideração uma das características dos números inteiros. Todos eles, exceto 2 e 3, têm a forma 6k ± 1. Isto significa que todos os inteiros podem ser expressos por (6k + i) onde, para um k qualquer, i = -1, 0, 1, 2, 3 ou 4. O inteiro 2 divide (6k + 0), (6k + 2) e (6k + 4); o inteiro 3 divide (6k + 3).

A primeira providência é dividir o número que está sendo testado por 2 e por 3. Depois, faz-se as divisões por todos os inteiros na forma 6k ± 1 que sejam menores ou iguais à raiz quadrada do número testado. Este algoritmo é três vezes mais rápido do que o método anterior.

Turbinando os testes de primalidade

Tanto os testes mencionados quanto outros métodos mais sofisticados podem ganhar em eficiência se tivermos uma lista dos primeiros números primos. Quanto maior for a lista, maior será o ganho. Antes de usar qualquer teste de primalidade, usa-se os primos da lista para fazer divisões sucessivas. Caso o número testado não seja divisível por nenhum deles, os novos testes, ao invés de partirem do inteiro 2, podem partir de uma base bem mais elevada.