Crivo de Eratóstenes com Complexidade de Tempo Linear

Dado um número $n$, encontre todos os números primos em um segmento $[2;n]$.

A maneira padrão de resolver uma tarefa é usar o crivo de Eratóstenes. Esse algoritmo é muito simples, mas possui tempo de execução $O(n \log \log n)$.

Embora existam muitos algoritmos conhecidos, com tempo de execução sublinear (i.e. $o(n)$), o algoritmo descrito abaixo é interessante por sua simplicidade: não é nem um pouco mais complexo que o clássico crivo de Eratóstenes.

Além disso, o algoritmo dado aqui calcula as fatorações de todos os números no segmento $[2; n]$ como efeito colateral, e isso pode ser útil em muitas aplicações práticas.

A fraqueza do algoritmo dado está em usar mais memória do que o clássico crivo de Eratóstenes: requer uma array de $n$ números, enquanto que para o crivo de Eratóstenes é suficiente ter $n$ bits de memória (que é 32 vezes menor).

Portanto, faz sentido usar o algoritmo descrito apenas até números da ordem $10^7$ e não maiores.

A autoria do algoritmo parece pertencer a Gries & Misra (Gries, Misra, 1978: ver referências no final do artigo). E, estritamente falando, esse algoritmo não deve ser chamado de "crivo de Eratóstenes", pois é muito diferente do clássico.

Algoritmo

Nosso objetivo é calcular o fator primo mínimo $lp [i]$ para todo número $i$ no segmento $[2; n]$.

Além disso, precisamos armazenar a lista de todos os números primos encontrados - vamos chamá-la de $pr []$.

Inicializaremos os valores $lp [i]$ com zeros, o que significa que assumimos que todos os números são primos. Durante a execução do algoritmo, essa array será preenchida gradualmente.

Agora iremos dos números de 2 até $n$. Temos dois casos para o número atual $i$:

Nos dois casos, atualizamos os valores de $lp []$ para os números divisíveis por $i$. No entanto, nosso objetivo é aprender a definir um valor $lp []$ no máximo uma vez para cada número. Podemos fazer da seguinte maneira:

Vamos considerar números $x_j = i \cdot p_j$, onde $p_j$ são todos números primos menores ou iguais à $lp [i]$ (é por isso que precisamos armazenar a lista de todos os números primos)..

Definiremos um novo valor $lp [x_j] = p_j$ para todos os números dessa forma.

A prova de correção desse algoritmo e seu tempo de execução podem ser encontrados após a implementação.

Implementação

const int N = 10000000;
int lp[N+1];
vector<int> pr;

for (int i=2; i<=N; ++i) {
    if (lp[i] == 0) {
        lp[i] = i;
        pr.push_back (i);
    }
    for (int j=0; j<(int)pr.size() && pr[j]<=lp[i] && i*pr[j]<=N; ++j)
        lp[i * pr[j]] = pr[j];
}

Podemos acelerar um pouco, substituindo o vetor $pr$ com uma simples array e um contador, e eliminando a segunda multiplicação no loop for (para isso, precisamos apenas lembrar o produto em uma variável).

Prova de Correção

Precisamos provar que o algoritmo define todos os valores $lp []$ corretamente e que todo valor será definido exatamente uma vez. Portanto, o algoritmo terá tempo de execução linear, pois todas as ações restantes do algoritmo funcionam por $O (n)$.

Note que todo número $i$ tem exatamente uma representação:

$i = lp [i] \cdot x$ ,

onde $lp [i]$ é o fator primo mínimo de $i$, e o número $x$ não tem nenhum fator primo menor que $lp [i]$, ou seja

$lp [i] \le lp [x]$.

Agora, vamos comparar isso com as ações do algoritmo: de fato, para cada $x$ ele passa por todos os números primos pelos quais pode ser multiplicado, ou seja, todos os números primos até $lp [x]$, a fim de obter os números na forma dada acima.

Portanto, o algoritmo passará por todos os números compostos exatamente uma vez, definindo os valores corretos de $lp []$.

Tempo de Execução e Memória

Apesar de o tempo de execução $O(n)$ ser melhor que $O(n \log \log n)$ do clássico crivo de Eratóstenes, a diferença entre eles não é muito grande. Na prática isso significa apenas o dobro da diferença de velocidade, e as versões otimizadas do crivo funcionam tão rápido quanto o algoritmo fornecido aqui.

Considerando os requisitos de memória desse algoritmo - uma array $lp []$ de tamanho $n$, e uma array $pr []$ de tamanho $\frac n {\ln n}$, esse algoritmo parece ser pior que o crivo clássica em todos os sentidos..

No entanto, sua qualidade permanece no fato de que ele calcular uma array $lp []$, o que nos permite encontrar a fatoração de qualquer número no segmento $[2; n]$ no tempo da ordem de tamanho dessa fatoração. Além disso, o uso de apenas uma array extra nos permitirá evitar divisões ao procurar a fatoração.

Conhecer as fatorações de todos os números é muito útil para algumas tarefas, e esse algoritmo é um dos poucos que permite encontrá-los em tempo linear.

Referências