Algoritmo para calcular o MMC

Este é um artigo bem básico. O objetivo dele é apresentar um algoritmo que permite calcular eficientemente o mínimo múltiplo comum (MMC) entre dois números naturais.

Como sempre, também apresento a implementação desse algoritmo em Java e em C.

Revisão Rápida de MMC

O MMC entre dois números naturais (vou me limitar ao conjunto dos números naturais) é o menor número natural que é múltiplo de ambos os números. Exemplos:

1. o MMC de 24 e 12 é igual a 24;
2. o MMC de 36 e 14 é igual a 252;
3. o MMC de 11 e 9 é igual a 99.

Uma das maneiras de calcular o MMC envolve a fatoração dos números em fatores primos, conforme o exemplo da imagem a seguir, que emprega um dispositivo prático, geralmente ensinado no ensino fundamental, para computar o MMC de 60 e 100 (cujo resultado é 300). Não irei detalhar como funciona o dispositivo, pois não é o objetivo da postagem.

Dispositivo prático para calcular o MMC

Outro método seria fatorando os números em potências inteiras de números primos e multiplicando apenas as maiores potências de cada primo:

• $60=2^2\times 3 \times 5$
• $100=2^2\times 5^2$

A maior potência de $2$ é $2^2$. A maior potência de $3$ é $3$. A maior potência de $5$ é $5^2$, logo

$$\operatorname{MMC}(60,100)=2^2\times 3 \times 5^2=300$$

O problema dos métodos anteriores é que a fatoração de números inteiros é um problema NP, não existindo um algoritmo que possa fazer isso de maneira eficiente.

A Relação entre o MMC e o MDC

O MMC e o MDC (máximo divisor comum) possuem uma propriedade muito interessante [1]:

$$\operatorname{MMC}(a,b)\times\operatorname{MDC}(a,b)=a\times b$$

Isto é, o produto de dois números é igual ao produto do MMC pelo MDC desses números.

Isolando o MMC na equação, temos

$$\operatorname{MMC}(a,b)=\frac{a\times b}{\operatorname{MDC}(a,b)}$$

Ou seja, podemos calcular o MMC utilizando o MDC. A vantagem disso é que o MDC pode ser calculado eficientemente através do algoritmo de Euclides, que foi apresentado numa postagem anterior do blog.

Portanto, basta implementar o algoritmo de Euclides e a fórmula anterior para calcular o MMC eficientemente e sem a necessidade de realizar a fatoração dos números.

Para evitar problemas de "estouro de variável" (overflow), é recomendado realizar a divisão antes da multiplicação:

$$\operatorname{MMC}(a,b)=a\times \frac{b}{\operatorname{MDC}(a,b)}= b\times \frac{a}{\operatorname{MDC}(a,b)}$$

Códigos

Os códigos a seguir implementam a fórmula apresentada anteriormente para calcular o MMC. Os mesmos já possuem o algoritmo de Euclides (versão iterativa) implementado.

MMC em Java

//Código por Henrique Felipe (GitHub: HenriqueIni)
public class MMC {
    //Algoritmo de Euclides iterativo
    private static int mdc(int a, int b){
        while(b != 0){
            int r = a % b;
            a = b;
            b = r;
        }
        return a;
    }
    //Algoritmo do MMC
    private static int mmc(int a, int b){
        return a * (b / mdc(a, b));
    }
    //Testes
    public static void main(String[] args) {
        System.out.println("MMC");
        System.out.printf("mmc(30, 60) = %d\n", mmc(30, 60));
        System.out.printf("mmc(60, 100) = %d\n", mmc(60, 100));
        System.out.printf("mmc(36, 14) = %d\n", mmc(36, 14));
    }    
}

MMC em C

//Código por Henrique Felipe (GitHub: HenriqueIni)
#include <stdio.h>
#include <stdlib.h>

//Algoritmo de Euclides iterativo
int mdc(int a, int b){
    while(b != 0){
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}
//Algoritmo do MMC
int mmc(int a, int b){
    return a * (b / mdc(a, b));
}
//Testes
int main() {
    printf("MMC\n");
    printf("mmc(30, 60) = %d\n", mmc(30, 60));
    printf("mmc(60, 100) = %d\n", mmc(60, 100));
    printf("mmc(36, 14) = %d\n", mmc(36, 14));
    return 0;
}

Referências

[1] SODRÉ, U., BENITO, R. (2006) ENSINO FUNDAMENTAL: Números naturais (II)