Fatoração de números inteiros via divisão por tentativa

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

• Algoritmo de Euclides: implementações e aplicações do MDC
• Algoritmo para calcular o MMC
• Fatorial em Java utilizando BigInteger
• Calculando números de Fibonacci com potenciação de matrizes

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.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55

//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.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59

//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.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

//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.