Pular para o conteúdo

MDC e Euclides

Aula 2 de 5 · 4 min

MDC e Euclides

Passo 1 de 7

O máximo divisor comum (MDC) é a régua mais longa que mede exatamente os dois comprimentos.

A ideia

O máximo divisor comum, o MDC (GCD), é a régua mais longa que mede os dois números com exatidão.

Encoste o comprimento menor no maior. O que sobra também precisa caber na mesma régua, então gcd(a, b) vira gcd(b, a % b). O par despenca em poucas divisões, e um resto zero entrega a resposta.

Exemplo do mundo real

Ferramentas de vídeo usam isso para simplificar proporções de tela: 1920 por 1080 têm MDC 120, e é daí que sai o “16:9”. A mesma redução mantém frações enxutas em motores de layout e em código de cobrança, onde o ponto flutuante acumularia desvios.

O código

Sua vez

Preencha a lacuna.

def gcd(a, b):
    while b:
        a, b = b, ___
    return a

Mini quiz

1 / 3

O que para o loop no algoritmo de Euclides?