Escrito por Leonardo Paes e Lúcio Figueiredo
Na matemática computacional há diversas maneiras de checar se um número é primo ou não, com diferentes algoritmos que possuem seus pontos fortes e fracos. Na aula de hoje, aprenderemos um algoritmo chamado de Crivo de Eratóstenes. Como o próprio nome sugere, seu criador foi Eratóstenes (a.C. 285-194 a.C.), um matemático grego.
Motivação Inicial
Imagine que precisamos resolver o seguinte problema: dado um número inteiro $$N$$, indique quantos números primos existem no intervalo $$[1, N]$$ (intervalo de $$1$$ a $$N$$, inclusive). Para resolver este problema, podemos utilizar um algoritmo bastante simples: para cada número $$v$$ no intervalo $$[1, N]$$, realizamos um teste de primalidade em $$v$$ – se o teste indicar que $$v$$ é primo, a resposta do problema aumenta em 1; senão, continua a mesma. Se utilizarmos o teste de primalidade apresentando na Aula 2, obtemos uma solução com complexidade $$O(N \sqrt{n})$$, já que iteramos por $$N$$ números e realizamos um teste de primalidade em $$O(\sqrt{n})$$ em cada um.
Perceba, porém, que para valores de $$N$$ maiores ou iguais a $$10^8$$, o algoritmo acima é muito ineficiente, necessitando de pelo menos $$10^{12}$$ operações! Felizmente, uma solução mais eficiente existe: o Crivo de Eratóstenes, que será apresentado a seguir.
Crivo de Eratóstenes
O algoritmo em si é bem simples:
- Escreva todos os números de $$2$$ até $$N$$. Inicialmente, nós não vamos considerá-los nem primos nem compostos (números que possuem mais que 2 divisores distintos).
- Pegue o primeiro número que ainda não foi marcado como composto e diga que ele é primo.
- A partir desse número primo, percorra todos os seus múltiplos até $$N$$ e marque-os como compostos. Eles necessariamente são compostos pois possuem como divisores, pelo menos, o número $$1$$, o primo atual e eles mesmos.
- Volte para o passo 2 até que todos os números sejam marcados como primos ou compostos.
A ideia por trás do algoritmo é a seguinte: Um número $$X$$ só é primo se nenhum outro primo no intervalo $$[1; X-1]$$ divide $$X$$. Como estamos iterando pelos números primos da esquerda para a direita, estamos marcando como compostos todos os números que são seus múltiplos. Então, se chegarmos em um número que não foi dito como composto $$\implies$$ ele é primo!
Visualização do algoritmo
Gif utilizado de: Wikipedia.
Código do algoritmo
Complexidade do Crivo de Eratóstenes
Você deve ter percebido que até agora não foi dito nada sobre a complexidade do algoritmo do Crivo. Nesta aula, provaremos que a sua complexidade é $$O(N \log_{} N)$$.
Para simplificar os cálculos, vamos assumir que $$N$$ é uma potência de $$2$$, ou seja $$N = 2^k$$, $$k \in \mathbb{Z}$$. Seja $$f(N)$$ a complexidade do algoritmo. Note que $$f(N)$$ é igual ao somatório, para cada primo $$p \leq N$$, do número de múltiplos de $$p$$ menores ou iguais a $$N$$; em outras palavras, $$f(n)$$ é igual ao somatório de $$\lfloor \frac{N}{p} \rfloor$$ para todo número primo $$p \leq N$$. Portanto, perceba que se em nosso algoritmo, ao invés de iterarmos por todos os múltiplos dos números primos, iterássemos pelos múltiplos de todos os números menores ou iguais a $$N$$, a complexidade resultante do algoritmo seria maior ou igual à do Crivo – ou seja, maior ou igual a $$f(N)$$. Logo, temos que,
$$\lfloor \frac{N}{1} \rfloor + \lfloor \frac{N}{2} \rfloor + \lfloor \frac{N}{3} \rfloor + … + \lfloor \frac{N}{N} \rfloor \geq f(N)$$.
Vamos agora supor que a quantidade de operações é ainda maior (ou seja, utilizar um limite superior ainda mais “frouxo” para $$f(N)$$). Ao invés de somarmos $$\lfloor \frac{N}{i} \rfloor $$ para cada $$i \leq N$$, vamos somar $$\frac{N}{2^{\lfloor{log_{2} \ i} \rfloor}} $$. Desse modo, o número total de operações (que continua maior que $$f(N)$$) é:
$$\frac{N}{2^{\lfloor{log_{2} \ 1} \rfloor}} + \frac{N}{2^{\lfloor{log_{2} \ 3} \rfloor}} + … + \frac{N}{2^{\lfloor{log_{2} \ N} \rfloor}} \geq f(N)$$
Agora, note que $$\lfloor log_{2} \ 2^k \rfloor = \lfloor log_{2} \ (2^k + 1) \rfloor = \lfloor \log_{2} (2^k + 2) \rfloor \ … \ = \lfloor log_{2} \ (2^k + (2^k – 1)) \rfloor$$, já que estamos calculando a parte inteira de cada logaritmo. Utilizando este fato, podemos concluir que a expressão acima é equivalente a
$$\underbrace{\frac{N}{2^{\lfloor{log_{} \ 2^0} \rfloor}}}_{2^0 \text{ vezes}} + \underbrace{\frac{N}{2^{\lfloor{log_{} \ 2^1} \rfloor}} + \frac{N}{2^{\lfloor{log_{} \ 2^1} \rfloor}}}_{2^1 \text{ vezes}} + \ … \ + \underbrace{\frac{N}{2^{\lfloor{log_{} \ N} \rfloor}} + \frac{N}{2^{\lfloor{log_{} \ N} \rfloor}} + \ … \ + \frac{N}{2^{\lfloor{log_{} \ N} \rfloor}}}_{2^{log_{} N} \text{ vezes}}$$
$$ = 2^0 \cdot \frac{N}{2^0} + 2^1 \cdot \frac{N}{2^1} + \ … \ + 2^{log_{} N} \cdot \frac{N}{2^{\log_{} N}} = \underbrace{N + N + \ … \ + N}_{\log_{} N \text{ vezes}} = N \cdot \log_{} N$$
Como vimos que $$f(N)$$ é menor ou igual à expressão calculada acima, obtemos que $$f(N) \leq N \log_{} N$$ $$\implies$$ complexidade do Crivo de Eratóstenes $$\in O(N \cdot \log_{} N)$$.
Obs.: Na demonstração acima assumimos que o valor $$N$$ era uma potência de $$2$$. Caso isto não fosse verdade, o resultado obtido seria bastante semelhante, com a diferença de que a expressão $$\frac{N}{2^{\lfloor{log_{2} \ 1} \rfloor}} + \frac{N}{2^{\lfloor{log_{2} \ 3} \rfloor}} + … + \frac{N}{2^{\lfloor{log_{2} \ N} \rfloor}}$$ seria igual a $$N \cdot \log_{} N + O(N)$$; ou seja, $$N \cdot \log_{} N$$ somado a um valor “de resto” menor ou igual a $$N$$. Portanto, a complexidade do algoritmo é a mesma em ambos os casos.
Apesar de termos provado que o Crivo possui complexidade $$O(N \log N)$$, é possível provar que o algoritmo é ainda mais eficiente, possuindo complexidade $$O(N \log_{} \log_{} N)$$. Como a demonstração deste fato requer conhecimentos de cálculo integral, não a mencionamos nesta aula; porém, caso queira conferi-la, leia este artigo (em inglês).
O Menor Fator Primo (SPF)
Uma das aplicações do Crivo de Eratóstenes é o cálculo do Menor Fator Primo de um inteiro, ou SPF (do inglês Shortest Prime Factor). Alguns exemplos de SPF:
$$SPF(10) = 2$$, já que $$10 = 2 \cdot 5$$.
$$SPF(39) = 3$$, já que $$39 = 3 \cdot 13$$.
$$SPF(5797) = 11$$, já que $$5797 = 11 \cdot 17 \cdot 31$$.
Para calcular o SPF de todos os números no intervalo $$[1, N]$$, basta fazer uma única modificação ao Crivo de Eratóstenes. Inicialmente, vamos declarar o vetor $$SPF[]$$, que indica o menor fator primo de um número, e vamos inicializá-lo com o valor $$0$$. Após isso, vamos executar o Crivo. Se no passo atual do algoritmo o primeiro número não marcado é o primo $$p$$, vamos identificar se $$p$$ é ou não o menor fator primo de cada um de seus múltiplos, conferindo para cada múltiplo $$j$$ de $$p$$ se $$SPF[j]$$ é igual a $$0$$; se sim, $$j$$ não foi marcado, e portanto $$p$$ é seu menor fator primo; caso contrário, seu menor fator primo já foi encontrado em um passo anterior do algoritmo. O código abaixo implementa esta modificação do Crivo para encontrar SPFs:
Fatoração em $$O(\log_{} N)$$
Imagine que queremos fatorar um número inteiro $$N$$ em primos, ou seja, encontrar todos os seus divisores primos. Um algoritmo que resolve este problema é aquele que foi apresentado na aula anterior, com complexidade $$O(\sqrt{N})$$. Porém, utilizando o Menor Fator Primo calculado pelo Crivo de Eratóstenes, conseguimos realizar fatorações em $$O(\log_{} N)$$.
Inicialmente, perceba que um número inteiro $$N$$ possui, no máximo, $$\log_{2} N$$ fatores primos, já que o menor número primo é $$2$$ e o maior expoente $$x$$ tal que $$2^x \leq N$$ é $$\log_{2} N$$. Utilizando o SPF, podemos iterar por todos os primos na fatoração de $$N$$ em ordem, da seguinte forma:
- Inicialmente, a lista de fatores primos de $$N$$ está vazia;
- Se $$N$$ for maior que $$1$$, insira $$SPF(N)$$ na lista de fatores primos; senão, termine o algoritmo;
- Repita o passo anterior fazendo $$N := \frac{N}{SPF(N)}.$$
Ou seja, primeiro inserimos $$SPF(N)$$ na lista, depois $$SPF(\frac{N}{SPF(N)})$$, e assim por diante, enquanto o número resultante for maior ou igual a $$1$$. Desta forma, conseguimos iterar por todos os fatores primos de $$N$$ em ordem. Como $$N$$ possui no máximo $$\log_{} N$$ fatores primos, a complexidade deste algoritmo de fatoração é $$O(\log_{} N)$$. O código abaixo implementa a fatoração de $$N$$ utilizando este método: