Algoritmo para calcular o MMC

Por
|  

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

Sugestões de livros para estudantes de computação na Amazon (patrocinado): Lista de Livros

Obrigado pela leitura! Se você puder, considere apoiar financeiramente o Blog Cyberini, Chave Pix: cyberpix9@gmail.com

Doar com PayPal

Siga o blog

Redes sociais: Facebook, Twitter, YouTube, Pinterest, Instagram, Telegram

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

8 comentários:

  1. Boa noite, como faço para usar mais de 2 números? Grato desde já =D

    ResponderExcluir
    Respostas
    1. Sim, você calcula o MMC dos dois primeiros, pega o resultado e calcula o MMC do resultado com o próximo número e assim sucessivamente.

      Exemplo: MMC(8, 12, 16, 32)

      Primeiro, você calcula o MMC de 8 e 12

      MMC(8, 12) = 24

      Agora, calculamos o MMC de 24 e 16

      MMC(24, 16) = 48

      Por fim, calculamos o MMC de 48 e 32

      MMC(48, 32) = 96

      Portanto, MMC(8, 12, 16, 32) = 96.

      Excluir
    2. Quase esqueci, mas tem um post no blog onde eu mostro como fazer o MMC de uma lista de números em Java, C e em JavaScript: MMC de uma lista de números

      Excluir
  2. Qual seria a complexidade desse algoritmo em notação O?
    seria um O(n)?

    ResponderExcluir
    Respostas
    1. Ele tem a mesma complexidade do algoritmo de Euclides no pior caso. Se você está calculando o MMC(a,b), a complexidade no pior caso será O(log(min(a,b))). Onde min(a,b) é o menor valor entre a e b. Se o menor é o a, então será O(log a), se o menor for o b, então vai ser O(log b).

      Excluir
  3. Certo! Não compreendi nada.
    não é a minha área. ;) :( :( ;( ;)

    ResponderExcluir
    Respostas
    1. Não pense assim, nem tudo é fácil, basta se esforçar

      Excluir