Algoritmos em Python

Máximo divisor comum com o algoritmo de Euclides em Python

Nesta lição, você vai encontrar o máximo divisor comum (MDC) de dois números com o algoritmo de Euclides.

  • Intermediário
  • 2 min de leitura
  • 1 exemplo executável

Introdução

O problema

Simplificar frações, dividir coisas em grupos iguais e muitos quebra-cabeças precisam do maior número que divide dois números. Testar cada candidato é lento para números grandes; Euclides encontrou um jeito muito mais rápido há mais de 2.000 anos.

Pense assim

O método de Euclides é como cobrir um retângulo com os maiores ladrilhos quadrados possíveis. Corte o maior quadrado que der de um retângulo de 48 × 18, depois do que sobrou, e continue. Quando as peças encaixam exatamente sem sobra, o lado do último quadrado é a resposta.

Dos quadrados cortados ao código
first, second▭ O retângulo: 48 × 18
first % second✂️ O que sobra depois de cortar quadrados do lado menor
first, second = second, first % second🔁 Repita com o pedaço que sobrou
while second:✅ Nada sobrou: o lado é o MDC, 6
gcd(a, b) = gcd(b, a % b) até o resto ser 0.
Em uma frase

O máximo divisor comum (MDC, em inglês GCD) de dois inteiros é o maior inteiro positivo que divide os dois. O algoritmo de Euclides o encontra trocando o par (a, b) por (b, a % b) até b ser 0.

Pontos-chave

  1. first, second = second, first % second troca o par pelo número menor e pelo resto.
  2. Para 48 e 18, os pares são (48, 18), (18, 12), (12, 6), (6, 0).
  3. while second: para quando o resto vira 0.
  4. return abs(first) dá um resultado positivo mesmo para entradas negativas.

Quando usar?

  • Simplificar frações e proporções.
  • Encontrar o mínimo múltiplo comum: a * b // gcd(a, b).
  • Quebra-cabeças numéricos, aritmética modular e noções de criptografia.

Quando não é preciso

  • Código real: math.gcd já vem pronto e aceita qualquer quantidade de argumentos nas versões recentes do Python.
  • Encontrar todos os divisores comuns: o MDC dá só o maior.

Código de exemplo

Executar código →
main.py
def gcd(first, second):
    while second:
        first, second = second, first % second
    return abs(first)

print(gcd(48, 18))
Gerar um botão Run para este exemplo

Resultado da execução

6

Explicação do código

A cada passo, o par (first, second) é substituído por (second, first % second). Quando o resto chega a 0, o valor que sobra em first é o MDC, então o MDC de 48 e 18 é 6. A função abs() garante que o resultado seja sempre positivo. O número de passos cresce muito devagar com o tamanho dos números, cerca de O(log n).

Altere os valores e execute o programa no compilador Python online CodeUtility sem instalar Python.

Exercícios práticos

Tente modificar o código seguindo as sugestões abaixo. Mudar o código e observar o resultado ajuda você a entender muito mais do que só ler.

  1. Teste com uma lista vazia, uma lista de um único elemento e uma lista com valores repetidos.
  2. Imprima o estado depois de cada passo para ver o algoritmo trabalhando.
  3. Meça o tempo com 100, 1.000 e 10.000 elementos e compare com outra solução.
Executar no compilador Python →

Erros comuns

Usar subtração em vez do resto

Subtrair várias vezes dá a mesma resposta, mas é muito lento para números distantes.

Problema
while first != second:
    if first > second:
        first -= second
    else:
        second -= first
Correção
while second:
    first, second = second, first % second

Terminou esta lição?

Marque como aprendida para acompanhar seu progresso.

Pratique com um desafio

Use o conteúdo desta lição para resolver um problema real. Cada desafio roda no navegador, com testes instantâneos e uma revisão por IA.

Todos os desafios