Matemática Computacional 02 - Teste de Primalidade, Divisores e Fatoração

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:

1. $d \leq \sqrt{N}$: Este caso é trivial, pois $d$ já é um divisor que satisfaz o lema.
2. $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:

1. Encontre o menor divisor $d$ de $N$ e adicione $d$ à fatoração.
2. Divida $N$ por $d$ até que o número resultante não seja mais um múltiplo de $d$.
3. 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: