Máximo divisor comum e mínimo múltiplo comum – algoritmos em C++

Um computador é muito rápido para executar operações matemáticas, mas infelizmente, ele não possui muita precisão para operações como divisão, ou multiplicação de números de ponto flutuante. Isto se torna um problema em algumas situações em que o truncamento é indesejado, como por exemplo, um cálculo de rota a partir de dados de um GPS.

A maneira mais razoável de lidar com isso é usar frações para representar números não-inteiros, mas racionais. Desta forma, podemos adiar o máximo possível os truncamentos, e em alguns casos até evitar que ele aconteça.

A operação com frações entretanto exige constantes ajustes de denominador, e algumas vezes de numerador, para que seja feita operações de soma e subtração, ou mesmo se evite o overflow dos inteiros que formam a fração. Assim, faz-se necessário o cálculo do máximo divisor comum (MDC), e do mínimo múltiplo comum (MMC).

Começaremos falando sobre o MDC. Existe duas formas principais pelas quais podemos obter o MDC. A primeira é iterativa, e parte de um raciocínio muito simples. Encontra-se o menor elemento entre os dois números, e a partir daí, começa-se testar um por um, todos os inteiros positivos menores que ele. O código para essa função é exposto abaixo:

     int MDC(int a,int b){ 

             int menor; 
             if (a>b)   menor =b; 
             else   menor =a;

             for (int i=menor; i>=1; i--)
                if (a%i==0 && b%i==0)
             
             return i;
}

É fácil perceber que este método é ineficiente pelas repetidas operações de módulo que são feitas, principalmente se os números forem muito grandes ou primos entre si. Mas o outro método, que é recursivo, tem passos muito mais rápidos rumo a resposta. Ele é uma implementação do algoritmo de Euclides, e encontra o MDC sem fazer nenhuma fatoração diretamente. Abaixo o código:

  int MDC(int a, int b) {     
           
           if (b==0) return a;

           return MDC(b,a%b);
}

Note que ele pega sempre o resto da divisão de um número pelo outro e passa adiante. São feitas então várias chamadas de função, até que o primeiro número seja divisivel pelo segundo (ou seja, o parâmetro b se anule). Note que este método é rápido para números grandes, pois a operação de módulo na chamada recursiva diminui drasticamente seu tamanho. Veja o caso do 358, 156, em que o MDC é 12:

Por fim, o cálculo do MMC sai quase que automaticamente do MDC, pois o MMC de dois números é o seu produto deles pelo MDC do par. Então:

    int MMC(int a,int b){
                 return a*b/MDC(a,b);
}