Escrito por Lúcio Figueiredo
Um dos problemas mais clássicos da matemática computacional consiste em encontrar maneiras eficientes para descobrir se um número é primo ou não, ou seja, realizar um teste de primalidade. Nesta aula, abordaremos um algoritmo simples para realizar testes de primalidade e encontrar divisores e fatores primos de um inteiro qualquer.
Teste de Primalidade em $$O(\sqrt{N})$$
Para checar se um certo número inteiro $$N$$ é primo ou não, podemos imaginar o seguinte simples algoritmo: Para cada número $$d$$ tal que $$2 \leq d < N$$, testamos se $$d$$ é um divisor de $$N$$, ou seja, se $$d \equiv 0 (mod \; N)$$. Se sim, $$N$$ é certamente um número composto. Senão, os únicos divisores de $$N$$ são $$1$$ e o próprio $$N$$, e logo, $$N$$ é um número primo.
O problema do algoritmo acima é que a sua complexidade é $$O(N)$$, o que, dependendo da situação, pode ser muito ineficiente. Para uma otimização significativa, vamos utilizar o seguinte lema:
Lema 1: Um número inteiro $$N$$ é composto se, e somente se este possui um divisor próprio $$d$$ (ou seja, um divisor diferente de $$1$$ e de $$N$$) menor ou igual a $$\sqrt{N}$$.
Prova: Se $$N$$ possui um divisor próprio menor ou igual a $$\sqrt{N}$$, $$N$$ certamente será composto. Vamos agora provar a outra parte, o “somente se”: Seja $$d$$ um divisor próprio qualquer de $$N$$. Perceba que $$\frac{N}{d}$$ também é um divisor próprio de $$N$$. Vamos analisar dois casos:
- $$d \leq \sqrt{N}$$: Este caso é trivial, pois $$d$$ já é um divisor que satisfaz o lema.
- $$d > \sqrt{N}$$: Neste caso, teremos que $$\frac{N}{d} < \frac{N}{\sqrt{N}} \implies \frac{N}{d} < \sqrt{N}$$. Logo, o divisor $$\frac{N}{d}$$ já torna o lema verdadeiro.
Como em ambos os casos o lema é verdadeiro, terminamos a prova.
Utilizando o lema acima, sabemos que um número é primo se, e somente se não possui nenhum divisor entre $$2$$ e $$\sqrt{N}$$. Logo, podemos otimizar nosso algoritmo inicial testando apenas se existe algum inteiro $$d$$ tal que $$2 \leq d \leq \sqrt{N}$$ e $$d$$ divide $$N$$. Assim, a complexidade do algoritmo otimizado será $$O(\sqrt{N})$$. Confira o código abaixo:
Divisores de um inteiro
Imagine que temos o seguinte problema: Dado um número inteiro $$N$$, queremos encontrar todos os divisores positivos de $$N$$. Uma possível solução seria, novamente, iterar por todos os números de $$1$$ a $$N$$ e checar quais deles dividem $$N$$, salvando-os em um vetor de respostas. Dessa forma, obtemos uma complexidade de $$O(N)$$.
Para otimizar este algoritmo, perceba que se $$p$$ é um divisor de $$N$$ maior que $$\sqrt{N}$$, então o número $$q = \frac{N}{p}$$ também é um divisor de $$N$$ e $$q < \sqrt{N}$$. Isso sugere que é suficiente iterarmos apenas pelos números de $$1$$ a $$\sqrt{N}$$, e, assim que encontrarmos um divisor $$q$$ tal que $$q \leq \sqrt{N}$$, inserimos tanto $$q$$ quanto $$\frac{N}{q}$$ em nosso vetor de respostas. Dessa forma, encontraremos tanto os divisores “pequenos” (menores ou iguais a $$\sqrt{N}$$) de $$N$$ quanto os divisores “grandes” (maiores que $$\sqrt{N}$$).
Confira o código para melhor entendimento:
Fatoração de um inteiro
Imagine que agora queremos encontrar todos os divisores primos de $$N$$, ou seja, queremos encontrar a fatoração de $$N$$ em números primos. Inicialmente, observe que o menor divisor próprio de um número composto é sempre um número primo. Além disso, pelo Lema 1, sabemos que este menor divisor é sempre menor ou igual a $$\sqrt{N}$$.
Estas duas observações indicam que podemos realizar o seguinte algoritmo:
- Encontre o menor divisor $$d$$ de $$N$$ e adicione $$d$$ à fatoração.
- Divida $$N$$ por $$d$$ até que o número resultante não seja mais um múltiplo de $$d$$.
- Repita os passos $$1$$ e $$2$$ até que o número resultante seja primo ou igual a $$1$$. Caso o número seja diferente de $$1$$, inclua-o na fatoração de $$N$$.
Essencialmente, iremos dividir o número $$N$$ sempre pelo seu menor fator, que é sempre um número primo, até que este fator não o divida mais. Desta maneira, o menor divisor do número resultante será o próximo divisor primo de $$N$$, e assim sucessivamente. Como o divisor $$d$$ será sempre menor ou igual a $$\sqrt{N}$$, a complexidade do algoritmo será (também!) $$O(\sqrt{N})$$.
Confira o código abaixo para melhor entendimento: