MDC em C++ - Como calcular o Máximo Divisor Comum

Vamos aprender como calcular o MDC de um número, ou seja, seu máximo divisor comum, usando recursão em C++. Primeiro, vamos entender o que é MDC.

O que é MDC ?

Todo número natural pode ser divido por outros, resultando em números naturais.
Por exemplo, o 8 pode ser dividido por:
8/1 = 8
8/2 = 4
8/4 = 2
8/8 = 1

O 11, que é um primo, pode ser dividido por:
11/1  = 11
11/11 = 1

Todo número natural tem, pelo menos, dois divisores: o 1 e ele mesmo.
Então, dois números naturais quaisquer, tem sempre algum divisor em comum, nem que seja apenas o 1.

É aí que entra o MDC, o máximo, queremos calcular o maior divisor comum, o maior divisor desses dois números.

Como calcular o MDC

Vamos calcular os divisores de 18:
18/1 = 18
18/2 = 9
18/3 = 6
18/6 = 3
18/9 = 2
18/18 = 1

Agora os divisores de 15:
15/1 = 15
15/3 = 5
15/5 = 3
15/15 = 1

1 e 3 são os números que se repetem, os divisores em comum. E qual o maior deles?
Pimba, é o 3!

Como calcular o MDC com C++ e recursão

O que vamos fazer é simples...vamos pegar o número maior e calcular o resto da divisão pelo menor.
Se der 0, acabou, o menor é o MDC.

Se não der 0, continuamos com mais alguns cálculos, até o resto da divisão do primeiro pelo segundo ser 0, mas pegamos duas coisas: o menor número e o resto da divisão do maior pelo menor.

Então, fazemos a recursividade, agora passando como argumentos o menor número e o resto da divisão do maior pelo menor.

Nosso código fica assim:

#include <iostream>
using namespace std;

int mdc(int num1, int num2)
{
    if(num1%num2 == 0)
        return num2;
    else
        return mdc(num2, num1%num2);
}

int main()
{
    int num1, num2;

    cout<<"Numeros (maior e menor): ";
    cin>> num1 >> num2;

    cout<<"MDC: "<<mdc(num1, num2)<<endl;
}

Para entender, matematicamente, a lógica anterior, você deve estudar o Algoritmo de Euclides.