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

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

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

?

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

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