Crivo de Eratóstenes

O Crivo de Eratóstenes é um algoritmo para encontrar todos os números primos em um segmento $[1;n]$ usando $O(n \log \log n)$ operações.

No começo, escrevemos todos os números entre 2 e $n$. Marcamos todos os múltiplos de 2 (já que 2 é o menor número primo) como composto. Um múltiplo adequado de um número $x$, é um número maior que $x$ e divisível por $x$. Em seguida, encontramos o próximo número que não foi marcado como composto, neste caso, é 3. O que significa que 3 é primo, e marcamos todos os múltiplos de 3 como compostos. O próximo número não marcado é 5, no qual é o próximo número primo, e marcamos todos os múltiplos apropriados. E continuamos esse procedimento até processarmos todos os números na linha.

Na imagem a seguir, você pode visualizar o algoritmo para calcular todos os números primos no intervalo $[1; 16]$.Note que muitas vezes marcamos números como compostos várias vezes.

Sieve of Eratosthenes

A idéia por trás é: um número é primo se nenhum dos números primos menores o dividir. Como iteramos os números primos em ordem, já marcamos todos os números(divisíveis por pelo menos um dos números primos) como divisíveis. Portanto, se alcançarmos uma célula e ela não estiver marcada, ela não será divisível por nenhum número primo menor e, portanto, terá que ser primo.

Implementação

int n;
vector<char> primo(n+1, true);
primo[0] = primo[1] = false;
for (int i = 2; i <= n; i++) {
    if (primo[i] && (long long)i * i <= n) {
        for (int j = i * i; j <= n; j += i)     //iteramos por todos os números divisíveis pelo primo i
            primo[j] = false;
    }
}

Esse código primeiro marca todos os números(exceto zero e um) como números primos em potencial, depois inicia o processo de selecionar os números compostos. Para isso, itera sobre todos os números de $2$ até $n$. Se o número atual $i$ for um número primo, ele marcará todos os números que são múltiplos de $i$ como números compostos, começando por $i^2$. Esta já é uma otimização sobre a implementação de força bruta, todos os números menores(que $i^2$) que são múltiplos de $i$ necessariamente também tem um fator primo menor que $i$, então todos eles foram analisados antes. Já que $i^2$ pode facilmente causar um overflow no tipo int, a análise adicional é feita com long long antes do segundo loop aninhado.

Usando essa implementação, o algoritmo consome $O(n)$ de memória e performa $O(n \log \log n)$ (veja a próxima seção).

Análise assintótica

Vamos provar que o tempo de execução do algoritmo é $O(n \log \log n)$. O algoritmo executará $\frac{n}{p}$ operações para todo primo $p \le n$, no loop interno. Portanto, precisamos avaliar a próxima expressão:

$$\sum_{\substack{p \le n, \\ p \text{ primo}}} \frac n p = n \cdot \sum_{\substack{p \le n, \\ p \text{ primo}}} \frac 1 p.$$

Vamos lembrar dois fatos conhecidos.

Assim, podemos escrever a soma da seguinte maneira:

$$\sum_{\substack{p \le n, \\ p \text{ primo}}} \frac 1 p \approx \frac 1 2 + \sum_{k = 2}^{\frac n {\ln n}} \frac 1 {k \ln k}.$$

Aqui, extraímos o primeiro número primo 2 da soma, pois $k = 1$ na aproximação $k \ln k$ é $0$ e causa uma divisão por zero.

Agora, vamos avaliar essa soma usando a integral de uma mesma função acima de $k$ de $2$ até $\frac n {\ln n}$ (podemos fazer essa aproximação pois, de fato, a soma está relacionada à integral como sua aproximação usando o método do retângulo):

$$\sum_{k = 2}^{\frac n {\ln n}} \frac 1 {k \ln k} \approx \int_2^{\frac n {\ln n}} \frac 1 {k \ln k} dk.$$

A antiderivada para o integrando é $\ln \ln k$. Usando uma substituição e removendo termos de ordem inferior, obteremos o resultado:

$$\int_2^{\frac n {\ln n}} \frac 1 {k \ln k} dk = \ln \ln \frac n {\ln n} - \ln \ln 2 = \ln(\ln n - \ln \ln n) - \ln \ln 2 \approx \ln \ln n.$$

Agora, voltando à soma original, obteremos sua aproximação:

$$\sum_{\substack{p \le n, \\ p\ é\ primo}} \frac n p \approx n \ln \ln n + o(n).$$

Você pode encontrar uma prova mais rigorosa (que fornece uma avaliação mais precisa) no livro de Hardy & Wright "Uma introdução à teoria dos números" (p. 349).

Diferentes otimizações

A maior fraqueza do algoritmo é que ele "percorre" a memória várias vezes, manipulando apenas elementos únicos. Isso não é muito amigável ao cache. E por causa disso, a constante que está oculta em $O(n \log \log n)$ é comparativamente grande.

Os métodos apresentados abaixo nos permitem reduzir a quantidade de operações executadas, bem como diminuir a memória consumida.

Selecionando até a raíz

Para encontrar todos os números primos até $n$, será suficiente realizar as análises(iterações) apenas pelos números primos que não excedam a raiz de $n$.

Os outros compostos depois da raiz de $n$ já estarão selecionados como não-primos(através da seleção de divisíveis pelo primo $x$, sendo $2 \le x \le \sqrt n$ ); o restante dos primos depois da raiz de $n$ não são selecionados e permanecem como verdadeiros na array.

int n;
vector<char> primo(n+1, true);
primo[0] = primo[1] = false;
for (int i = 2; i <= sqrt(n); i++) {   
    if (primo[i]) {
        for (int j = 2; i*j <= n; j++)
            primo[i*j] = false;   //multiplos de i não são primos, pois são divisiveis por i(primo)
    }
}

Essa otimização não afeta a complexidade (de fato, repetindo a prova apresentada acima, obteremos a expressão $n \ln \ln \sqrt n + o(n)$, que é assintoticamente o mesmo de acordo com as propriedades dos logaritmos ), embora o número de operações seja reduzido notavelmente.

Selecionando apenas pelos números ímpares

Como todos os números pares (exceto $2$) são compostos, podemos parar de verificar os números pares. Em vez disso, precisamos operar apenas com números ímpares.

Primeiro, permitirá metade da memória necessária. Segundo, reduzirá o número de operações executadas pelo algoritmo aproximadamente pela metade.

Reduzindo a memória consumida

Devemos notar que o algoritmo de Eratóstenes opera com $n$ bits de memória. Portanto, podemos essencialmente reduzir a memória consumida preservando não $n$ bytes, que são as variáveis do tipo Booleano, mas $n$ bits, ou seja, $\frac n 8$ bytes de memória.

No entanto, essa abordagem, na qual é chamada compressão de dados, complicará as operações com esses bits. A operação de leitura ou escritura em qualquer bit requer várias operações aritméticas e, finalmente, torna o algoritmo mais lento.

Portanto, essa abordagem é justificada apenas se n for tão grande que não possamos mais alocar n bytes de memória. Nesse caso, trocaremos a economia de memória (8 vezes menos) com uma desaceleração significativa do algoritmo.

Vale a pena mencionar que existem estruturas de dados que fazem automaticamente uma compactação no nível de bits, como vector<bool> e bitset<> no C++.

Selecionando por blocos

Segue da otimização "selecionando até a raiz" que não há necessidade de manter a array inteira primo[1...n] todo o tempo. Basta manter apenas números primos até a raiz de $n$, i.e. primos[1... sqrt(n)], dividir o intervalo completo em blocos e selecionar cada bloco separadamente. Ao fazer isso, nunca precisamos manter vários blocos na memória ao mesmo tempo, e a CPU lida com o cache muito melhor.

Deixe que $s$ seja a constante na qual determina o tamanho do bloco, assim teremos $\lceil {\frac n s} \rceil$ blocos, e o bloco $k$ ($k = 0 ... \lfloor {\frac n s} \rfloor$) contém os números em um segmento $[ks; ks + s - 1]$. Podemos trabalhar com blocos apenas por turnos, ou seja, para cada bloco $k$ nós passaremos por todos os números primos (de $1$ até $\sqrt n$) e performaremos a seleção usando eles. Vale ressaltar que precisamos modificar um pouco a estratégia ao lidar com os primeiros números: primeiro, todos os números primos de $[1; \sqrt n]$ não devem se remover; e segundo, os números $0$ e $1$ devem ser marcados como números não primos. Enquanto estiver trabalhando no último bloco, não se deve esquecer que o último número $n$ não está necessariamente encontrado no final do bloco.

Aqui temos uma implementação que conta o número de números primos menores ou iguais a $n$ usando seleção por blocos.

int contar_primos(int n) {
    const int S = 10000;

    vector<int> primos;    //array com os números primos
    int nsqrt = sqrt(n);
    vector<char> primo(nsqrt + 1, true);  //array para ver se é primo ou não
    for (int i = 2; i <= nsqrt; i++) {
        if (primo[i]) {
            primos.push_back(i);
            for (int j = i * i; j <= nsqrt; j += i)   //iteramos até a raiz de n
                primo[j] = false;
        }
    }

    int result = 0;
    vector<char> block(S);  //array dos blocos
    for (int k = 0; k * S <= n; k++) {   //dividindo o intervalo em blocos 
        fill(block.begin(), block.end(), true);
        int inicio = k * S;
        for (int p : primos) {
            int inicio_idx = (inicio + p - 1) / p;
            int j = max(inicio_idx, p) * p - inicio;
            for (; j < S; j += p)
                block[j] = false;
        }
        if (k == 0)
            block[0] = block[1] = false;
        for (int i = 0; i < S && start + i <= n; i++) {  //selecionando os blocos
            if (block[i])
                result++;
        }
    }
    return result;   //quantidade de números primos
}

O tempo de execução da seleção por blocos é o mesmo da seleção regular do Crivo de Eratóstenes (a menos que o tamanho dos blocos seja muito pequeno), mas a memória necessária será reduzida para $O(\sqrt{n} + S)$ e teremos melhores resultados de cache. Por outro lado, haverá uma divisão para cada par de um bloco e número primo de $[1; \sqrt{n}]$, e isso será muito pior para tamanhos de bloco menores. Portanto, é necessário manter o equilíbrio ao selecionar a constante $S$. Obtemos melhores resultados para tamanhos de bloco entre $10^4$ e $10^5$.

Modificação para tempo linear

Podemos modificar o algoritmo de tal maneira que ele só tenha complexidade de tempo linear. Essa abordagem é descrita no artigo Crivo de Eratóstenes com Complexidade de Tempo Linear. No entanto, esse algoritmo também possui suas próprias fraquezas.

Problemas