GCD (MDC) – Algoritmo de Euclides

Depois de executar várias iterações do algoritmo, começamos a perceber que existem algumas operações redundantes, e o processo de encontrar o máximo divisor comum pode, na verdade, ser otimizado.

Usando subtração, continuamos a subtrair o número menor do número maior até obtermos 0 ou um valor que seja igual ao MDC. Podemos acelerar esse procedimento ao encontrar o resto da divisão do número maior pelo número menor. Com a operação de módulo, dividimos repetidamente o número maior pelo menor e tomamos o resto até que esse resto seja 0. O último resto não nulo que obtemos é o MDC.

Pense na operação de módulo como um modo mais eficiente de encontrar o MDC. Em vez de subtrair continuamente o número menor do número maior, utilizamos a divisão para reduzir o número maior. Isso significa que estamos dividindo ambos os números pelos seus divisores comuns e, assim, convergindo para o maior divisor comum de forma muito mais rápida.

a, b = int(input()), int(input())
while a > 0 and b > 0:  # Se a ou b for 0 => o outro será o GCD
    a, b = b, a % b     # O gcd de (a, b) é o mesmo que o gcd de (b, a % b)

d = b if a == 0 else a  # se a = 0 => b é o GCD, se b = 0 => a é o GCD
print('gcd:', d)

Este algoritmo foi mencionado pela primeira vez no livro de Euclides, escrito em 300 a.C.

Vamos fazer algumas simulações do algoritmo:

Entrada

A única linha da entrada contém dois inteiros a e b (0 ≤ a, b ≤ ).

Saída

O programa deve imprimir o máximo divisor comum de a e b.

Exemplos