Candidatos a primos

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.