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é √n. Isto é, se p
é o fator analisado, então a seguinte condição deve ser satisfeita: p2≤n.
A justificativa é que se p
é divisor de n
, então n=p×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×q, então pelo menos um dos fatores não deve ultrapassar √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.
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.
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