Em computação, a fatoração de números inteiros é um problema NP e não se sabe se existe um algoritmo polinomial capaz de resolver esse problema.
É claro, o fato de não sabermos da existência de um algoritmo polinomial não implica que não existem algoritmos que realizam a fatoração.
Neste artigo, apresento um algoritmo que faz a fatoração via força bruta chamado de "divisão por tentativa". O algoritmo é exato, isto é, dado um número inteiro qualquer, o algoritmo irá retornar uma lista com os fatores desse número. Entretanto, ele faz a fatoração em tempo exponencial.
Além do algoritmo, também apresento implementações do mesmo em Java, C e JavaScript.
Algoritmo de divisão por tentativa
A ideia do algoritmo é bem simples: dado um número n, verificamos se cada número menor do que n é seu divisor.
Por exemplo, para n = 8, teríamos
- 8 é divisível por 1;
- 8 é divisível por 2;
- 8 não é divisível por 3;
- 8 é divisível por 4;
- 8 não é divisível por 5;
- 8 não é divisível por 6;
- 8 não é divisível por 7;
- 8 é divisível por 8.
Percebe-se claramente que se o número for grande, o algoritmo será bem lento, por isso é conveniente realizar alguma otimização.
Na prática, não precisamos checar todos os valores até n. É suficiente verificar somente até $\sqrt{n}$. Isto é, se p é o fator analisado, então a seguinte condição deve ser satisfeita: $p^2 \leq n$.
A justificativa é que se p é divisor de n, então $n = p \times q$ e que se $q < p$, então q ou um dos seus fatores primos deveria ter sido detectado previamente como um divisor de n [2].
Além disso, se $n = p\times q$, então pelo menos um dos fatores não deve ultrapassar $\sqrt{n}$, senão o produto seria maior que n [1].
O algoritmo, em pseudocódigo, é
01. trialDivision(n) 02. | para d ← 2 até √n 03. | | enquanto(n % d = 0) 04. | | | imprima d 05. | | | n ← n / d 06. | | fim_enquanto 07. | fim_para 08. | imprima n 09. fim_trialDivision
Mas podemos melhorar. O algoritmo anterior irá imprimir apenas fatores primos de n, incluindo repetições. Sabemos que todos os primos, exceto 2, são ímpares. Então podemos verificar se 2 é um fator separadamente e depois utilizamos um laço para verificar apenas números ímpares. Isso reduz o custo pela metade. Em pseudocódigo, temos (o algoritmo a seguir é da Wikipédia, mas com algumas alterações) [2]
01. trialDivision(n) 02. | enquanto(n % 2 = 0) 03. | | imprima 2 04. | | n ← n / 2 05. | fim_enquanto 06. | d ← 3 07. | enquanto(d2 ≤ n) 08. | | se(n % d = 0) 09. | | | imprima d 10. | | | n ← n / d 11. | | senão 12. | | | d ← d + 2 13. | | fim_se 14. | fim_enquanto 15. | se(n > 1) 16. | | imprima n 17. | fim_se 18. fim_trialDivision
O laço das linhas 2-5 imprime todas as ocorrências do fator 2 em n (se houver). A variável d (linha 6) conterá os possíveis fatores ímpares de n (afinal, não haverá mais pares).
O laço das linhas 7-14 verifica exaustivamente os divisores ímpares de n, começando pelo 3, até que não haja mais divisores para verificar. Se algum número não for fator de n ou se já verificamos todas as ocorrências daquele fator, o laço pula para o próximo ímpar na linha 12.
Observe que o laço será executado enquanto d2 for menor ou igual a n, que é equivalente a verificar se d não ultrapassa a raiz quadrada de n.
A condição nas linhas 15-17 é necessária porque se n for primo, então a condição da linha 8 sempre será falsa. Além disso, uma vez que nunca ultrapassaremos √n nas iterações, então o valor da variável d nunca alcançará n.
O algoritmo irá imprimir apenas fatores primos, pois à medida que eliminamos a ocorrência de um fator, também eliminamos a ocorrência dos múltiplos daquele fator. A ideia é similar ao Crivo de Erastóstenes.
Por fim, conforme mencionei no início do artigo, o algoritmo de divisão por tentativa tem complexidade exponencial, portanto ele é inviável para números grandes.
Leia também
Códigos
Os códigos são apresentados a seguir
Código em Java
O código em Java a seguir armazena os fatores numa lista ligada, mas você pode utilizar a estrutura de dados que quiser. A lista irá conter todos os fatores primos do número fatorado, incluindo as repetições.
//GitHub: HenriqueIni
import java.util.LinkedList;
import java.util.List;
// Algoritmo de fatoração 'divisão por tentativa' (Trial Division)
public class TrialDivision {
// Retorna uma lista de fatores primos de n
// Se quiser, substitua 'int' por 'long'
public static List<Integer> trialDivision(int n){
// O fatores são armazenados numa lista ligada
// Entretanto você pode usar a estrutura que quiser
// Exemplos: Array, ArrayList, Stack (pilha)
List<Integer> factors = new LinkedList<Integer>();
// Verifica se 2 é fator
while(n % 2 == 0){
factors.add(2);
n = n / 2;
}
// Agora verifica os possíveis fatores ímpares
// Só ímpares são possíveis
int d = 3; // Possíveis fatores
int d2 = 9; // d2 = d * d
while(d2 <= n){
// Se d é fator, faz a divisão e armazena o fator
if(n % d == 0){
factors.add(d);
n = n / d;
}else{
// Se d não é fator, verifica o próximo
d = d + 2;
d2 = d * d; // d2 = d*d
}
}
// Essa condição é necessária quando n for primo
if(n > 1){
factors.add(n);
}
return factors;
}
// Testes
public static void main(String[] args) {
System.out.println("Fatores de 10 = " + trialDivision(10));
System.out.println("Fatores de 50 = " + trialDivision(50));
System.out.println("Fatores de 24 = " + trialDivision(24));
System.out.println("Fatores de 350 = " + trialDivision(350));
System.out.println("Fatores de 107 = " + trialDivision(107));
System.out.println("Fatores de 1025 = " + trialDivision(1025));
System.out.println("Fatores de 3 * 5 * 7 * 11 * 13 * 17 = " +
trialDivision(3 * 5 * 7 * 11 * 13 * 17));
}
}
Código em C
Ao contrário do código em Java, o código em C a seguir imprime os fatores ao invés de armazená-los em alguma estrutura de dados.
//GitHub: HenriqueIni
#include <stdio.h>
#include <stdlib.h>
// Imprime os fatores primos de n
// Se quiser, substitua 'int' por 'long'
void trialDivision(int n){
// Verifica se 2 é fator
while(n % 2 == 0){
printf("%d, ", 2);
n = n / 2;
}
// Agora verifica os possíveis fatores ímpares
// Só ímpares são possíveis
int d = 3; // Possíveis fatores
int d2 = 9; // d2 = d * d
while(d2 <= n){
// Se d é fator, faz a divisão e imprime o fator
if(n % d == 0){
printf("%d, ", d);
n = n / d;
}else{
// Se d não é fator, verifica o próximo
d = d + 2;
d2 = d * d; // d2 = d*d
}
}
// Essa condição é necessária quando n for primo
if(n > 1){
printf("%d, ", n);
}
printf("\n");
}
int main() {
printf("Fatores de 10 = ");
trialDivision(10);
printf("Fatores de 50 = ");
trialDivision(50);
printf("Fatores de 24 = ");
trialDivision(24);
printf("Fatores de 350 = ");
trialDivision(350);
printf("Fatores de 107 = ");
trialDivision(107);
printf("Fatores de 1025 = ");
trialDivision(1025);
printf("Fatores de 3 * 5 * 7 * 11 * 13 * 17 = ");
trialDivision(3 * 5 * 7 * 11 * 13 * 17);
return 0;
}
Código em JavaScript
O código em JavaScript a seguir contém apenas a função que realiza a fatoração.
//GitHub: HenriqueIni
// Algoritmo de fatoração 'divisão por tentativa' (Trial Division)
// Retorna uma lista de fatores primos de n
function trialDivision(n){
// O fatores são armazenados num array
var factors = [];
// Verifica se 2 é fator
while(n % 2 == 0){
factors.push(2);
n = n / 2;
}
// Agora verifica os possíveis fatores ímpares
// Só ímpares são possíveis
var d = 3; // Possíveis fatores
var d2 = 9; // d2 = d * d
while(d2 <= n){
// Se d é fator, faz a divisão e armazena o fator
if(n % d == 0){
factors.push(d);
n = n / d;
}else{
// Se d não é fator, verifica o próximo
d = d + 2;
d2 = d * d; // d2 = d*d
}
}
// Essa condição é necessária quando n for primo
if(n > 1){
factors.push(n);
}
return factors;
}
Referências
- [1] AMIT, ALON (23 de junho 2016). What is trial division method for factorization? How is it implemented? Is it fit for large numbers?. Acesso em 23 de abril de 2018.
- [2] Wikipédia. Trial division. Acesso em 23 de abril de 2018.
so faltou explicar o pq do algoritmo ser exponencial, mas a explicação sobre so precisar ir até a raiz quadrada pra achar os primos foi útil.
ResponderExcluir