MMC de uma lista de números

O MMC (mínimo múltiplo comum) entre dois números inteiros pode ser facilmente calculado com o auxílio do MDC [3], sem a necessidade de realizar a fatoração dos números.

Contudo, quando precisamos calcular o MMC entre três ou mais números, a situação muda, pois o algoritmo convencional não pode ser empregado de forma direta.

Veja também: Calculadora online de MMC (mínimo múltiplo comum)

Felizmente, o MMC possui a seguinte propriedade [1]:

MMC(x,y,z) = MMC(x, MMC(y,z)) = MMC(MMC(x,y), z)

Essa propriedade recursiva pode ser estendida para uma lista de tamanho genérico.

MMC(a, b, c,..., z) = MMC(a, MMC(b, c,..., z)) = MMC(a, MMC(b, MMC(c,..., z)))

Portanto, se conhecemos um algoritmo para calcular o MMC entre dois números, então podemos utilizar esse algoritmo para calcular o MMC de uma lista de números.

Como exemplo, vamos calcular o MMC de 49, 14, 77 e 63:

MMC(49, 14, 77, 63) = MMC(49, MMC(14, 77, 63)) 
	= MMC(49, MMC(14, MMC(77, 63))) 
	= MMC(49, MMC(14, 693)) 
	= MMC(49, 1386) 
	= 9702

Em pseudocódigo teríamos

01. mmcLista(A[1...n])
02. |   resultado ← A[1]
03. |   para i ← 2 até n
04. |   |   //mmc é qualquer algoritmo que calcula o MMC entre dois números
05. |   |   resultado ← mmc(resultado, A[i])
06. |   fim_para
07. fim_mmcLista

Código em Java:

//Código por Henrique Felipe (GitHub: HenriqueIni)
//www.blogcyberini.com
public class MMCLista {
    //Algoritmo de Euclides iterativo para calcular MDC
    public static int mdc(int a, int b){        
        while(b != 0){
            int r = a % b;
            a = b;
            b = r;
        }
        return a;
    }
    
    //Calcula o MMC de uma lista de números
    public static int mmcLista(int[] numberList){
        if(numberList.length < 2){
            throw new IllegalArgumentException("A lista deve conter pelo menos dois números");
        }
        int mmcResultado = numberList[0];
        for(int i = 1; i < numberList.length; i++){
            mmcResultado = mmcResultado * (numberList[i] / mdc(mmcResultado, numberList[i]));
        }
        return mmcResultado;
    }
    
    //código de testes
    public static void main(String[] args) {
        System.out.println("MMC(2,3,4,5) = " + mmcLista(new int[]{2,3,4,5}));
        System.out.println("MMC(1024, 4, 24, 12) = " + mmcLista(new int[]{1024, 4, 24, 12}));
        System.out.println("MMC(49, 14, 77, 63) = " + mmcLista(new int[]{49, 14, 77, 63}));
        System.out.println("MMC(100, 20) = " + mmcLista(new int[]{100, 20}));
    }
}

Código em C:

//Código por Henrique Felipe (GitHub: HenriqueIni)
//www.blogcyberini.com
#include <stdio.h>
#include <stdlib.h>
 
//Algoritmo de Euclides iterativo para calcular MDC
int mdc(int a, int b){
    while(b != 0){
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}
//Calcula o MMC de uma lista de números
int mmcLista(int n, int numberList[]){
    int mmcResultado = numberList[0];
    int i;
    for(i = 1; i < n; i++){
        mmcResultado = mmcResultado * (numberList[i] / mdc(mmcResultado, numberList[i]));
    }
    return mmcResultado;
}
//código de testes
int main() {
    int A[4] = {2,3,4,5};
    int B[4] = {1024, 4, 24, 12};
    int C[4] = {49, 14, 77, 63};
    int D[2] = {100, 20};    
    
    printf("MMC(2,3,4,5) = %d\n", mmcLista(4, A));
    printf("MMC(1024, 4, 24, 12) = %d\n", mmcLista(4, B));
    printf("MMC(49, 14, 77, 63) = %d\n", mmcLista(4, C));
    printf("MMC(100, 20) = %d\n", mmcLista(2, D));
    return 0;
}

Código em JavaScript:

//Código por Henrique Felipe (GitHub: HenriqueIni)
//www.blogcyberini.com

//Algoritmo de Euclides iterativo para calcular MDC
function mdc(a, b) {
    while (b !== 0) {
        var r = a % b;
        a = b;
        b = r;
    }
    return a;
}
//Calcula o MMC de uma lista de números
function mmcLista(numberList) {
    var mmcResultado = numberList[0];
    var i;
    for (i = 1; i < numberList.length; i++) {
        mmcResultado = (mmcResultado * numberList[i])/mdc(mmcResultado, numberList[i]);
    }
    return mmcResultado;
}
//código de testes
function tests() {
    var output = "";
    output += "MMC(2,3,4,5) = " + mmcLista([2, 3, 4, 5]) + "\n";
    output += "MMC(1024, 4, 24, 12) = " + mmcLista([1024, 4, 24, 12]) + "\n";
    output += "MMC(49, 14, 77, 63) = " + mmcLista([49, 14, 77, 63]) + "\n";
    output += "MMC(100, 20) = " + mmcLista([100, 20]);
    alert(output);
}

Referências

• [1] GeeksforGeeks. LCM of given array elements. Acesso em 8 de agosto de 2018.
• [2] Felipe, H (2018). Algoritmo de Euclides: implementações e aplicações do MDC. Acesso em 31 de julho de 2018.
• [3] Felipe, H (2018). Algoritmo para calcular o MMC. Acesso em 10 de agosto de 2018.