Quem sair a procurar primos não se dará ao trabalho de inspecionar os inteiros pares. Então, começando pelo primeiro inteiro não múltiplo de 2, basta ir somando 2 para encontrar aqueles que não são múltiplos de 2. Ou seja, há aí uma pequena série (2).
Resolvi investigar o que apareceria se eu quisesse eliminar também os múltiplos de 3. Começando com 5 (o primeiro inteiro que não é múltiplo nem de 2 nem de 3), descobri que basta somar 2, depois 4, depois 2, depois 4 e assim por diante. Então, a nova série é (2, 4).
Confiante com o sucesso, busquei, com a ajuda de um script em Perl, as séries para os primos seguintes. O que facilita a busca é que a soma dos elementos tem que ser igual ao produto dos primos que queremos excluir. Então, para 2 e 3 a nossa série é (2, 4), cuja soma é igual e 2*3.
A série para 2, 3 e 5 é (4, 2, 4, 2, 4, 6, 2, 6). A partir daí, as séries crescem seriamente. A tabela abaixo mostra a quantidade de elementos para cada uma:
| Primos | Elementos na série |
|---|---|
| 2 | 1 |
| 2, 3 | 2 |
| 2, 3, 5 | 8 |
| 2, 3, 5, 7 | 48 |
| 2, 3, 5, 7, 11 | 480 |
| 2, 3, 5, 7, 11, 13 | 5.760 |
| 2, 3, 5, 7, 11, 13, 17 | 92.160 |
| 2, 3, 5, 7, 11, 13, 17, 19 | 1.658.880 |
| 2, 3, 5, 7, 11, 13, 17, 19, 23 | 36.495.360 |
Quando tentei calcular a série para os primos até 29, a memória acabou. Cada série tem o número de elementos da série anterior vezes o novo primo menos um. A série dos 4 primeiros primos, por exemplo, tem 6 vezes mais elementos que a série para os 3 primeiros primos, porque adicionou o 7. A próxima série da minha tabela, portanto, deve ter 1.021.870.080 elementos (28 vezes mais que a anterior).
Usando a primeira série, reduz-se o domínio de busca pela metade (inspecionam-se apenas os ímpares). Com a segunda, resta apenas um terço (a série cobre 1/2+1/3-1/6 dos inteiros). Usando a série dos quatro primeiros primos, é preciso inspecionar apenas cerca de 22,8% dos inteiros. Logo, vê-se que a vantagem de usar séries que cobrem mais primos vai diminuindo rapidamente.
