MDC de uma lista de números

É sabido que MDC (máximo divisor comum) entre dois números inteiros pode ser facilmente calculado através do Algoritmo de Euclides. Entretanto, como fazer para calcular o MDC de uma lista de números?

Veja também: Calculadora online de MDC (máximo divisor comum)

O MDC entre três números, por exemplo, é igual ao MDC entre o primeiro número e o MDC dos outros dois [1]

MDC(x,y,z) = MDC(x, MDC(y,z)) = MDC(MDC(x,y), z)

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

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

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

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

MDC(49, 14, 77, 63) = MDC(49, MDC(14, 77, 63)) 
	= MDC(49, MDC(14, MDC(77, 63))) 
	= MDC(49, MDC(14, 7)) 
	= MDC(49, 7) 
	= 7

Em pseudocódigo teríamos

01. mdcLista(A[1...n])
02. |   resultado ← A[1]
03. |   para i ← 2 até n
04. |   |   //mdc é qualquer algoritmo que calcula o MDC entre dois números (como o de Euclides)
05. |   |   resultado ← mdc(resultado, A[i])
06. |   fim_para
07. fim_mdcLista

Código em Java:

//Código por Henrique Felipe (GitHub: HenriqueIni)
//www.blogcyberini.com
public class MDCLista {
    //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 MDC de uma lista de números
    public static int mdcLista(int[] numberList){
        if(numberList.length < 2){
            throw new IllegalArgumentException("A lista deve conter pelo menos dois números");
        }
        int mdcResultado = numberList[0];
        for(int i = 1; i < numberList.length; i++){
            mdcResultado = mdc(mdcResultado, numberList[i]);
        }
        return mdcResultado;
    }
    
    //código de testes
    public static void main(String[] args) {
        System.out.println("MDC(2,3,4,5) = " + mdcLista(new int[]{2,3,4,5}));
        System.out.println("MDC(1024, 4, 24, 12) = " + mdcLista(new int[]{1024, 4, 24, 12}));
        System.out.println("MDC(49, 14, 77, 63) = " + mdcLista(new int[]{49, 14, 77, 63}));
        System.out.println("MDC(100, 20) = " + mdcLista(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 MDC de uma lista de números
int mdcLista(int n, int numberList[]){
    int mdcResultado = numberList[0];
    int i;
    for(i = 1; i < n; i++){
        mdcResultado = mdc(mdcResultado, numberList[i]);
    }
    return mdcResultado;
}
//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("mdc(2,3,4,5) = %d\n", mdcLista(4, A));
    printf("mdc(1024, 4, 24, 12) = %d\n", mdcLista(4, B));
    printf("mdc(49, 14, 77, 63) = %d\n", mdcLista(4, C));
    printf("mdc(100, 20) = %d\n", mdcLista(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 MDC de uma lista de números
function mdcLista(numberList) {
    var mdcResultado = numberList[0];
    var i;
    for (i = 1; i < numberList.length; i++) {
        mdcResultado = mdc(mdcResultado, numberList[i]);
    }
    return mdcResultado;
}

Referências

• [1] GeeksforGeeks. GCD of more than two (or array) numbers. Acesso em 31 de julho de 2018.
• [2] Felipe, H (2018). Algoritmo de Euclides: implementações e aplicações do MDC. Acesso em 31 de julho de 2018.