Matemática Computacional 03 - Crivo de Eratóstenes e o Menor Fator Primo

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:

1.  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).
2.  Pegue o primeiro número que ainda não foi marcado como composto e diga que ele é primo.
3.  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.
4.  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:

1. Inicialmente, a lista de fatores primos de $N$ está vazia;
2. Se $N$ for maior que $1$, insira $SPF(N)$ na lista de fatores primos; senão, termine o algoritmo;
3. 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: