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

Por
|

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.

Algoritmo de divisão por tentativa para a fatoração de números inteiros

É 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

Siga o blog por e-mail

Receba notificações de novas postagens e novidades do blog por e-mail.

Importante: utilize o bom senso na hora de comentar. Acesse a política de privacidade para maiores informações sobre comentários.

Nenhum comentário:

Postar um comentário