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.
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.
first, second▭ O retângulo: 48 × 18first % second✂️ O que sobra depois de cortar quadrados do lado menorfirst, second = second, first % second🔁 Repita com o pedaço que sobrouwhile second:✅ Nada sobrou: o lado é o MDC, 6O 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
first, second = second, first % secondtroca o par pelo número menor e pelo resto.- Para 48 e 18, os pares são (48, 18), (18, 12), (12, 6), (6, 0).
while second:para quando o resto vira 0.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.gcdjá 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
def gcd(first, second):
while second:
first, second = second, first % second
return abs(first)
print(gcd(48, 18))
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.
- Teste com uma lista vazia, uma lista de um único elemento e uma lista com valores repetidos.
- Imprima o estado depois de cada passo para ver o algoritmo trabalhando.
- Meça o tempo com 100, 1.000 e 10.000 elementos e compare com outra solução.
Erros comuns
Usar subtração em vez do resto
Subtrair várias vezes dá a mesma resposta, mas é muito lento para números distantes.
while first != second:
if first > second:
first -= second
else:
second -= first
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.
- Maior Divisor Comum Encontre o maior número que divide ambos os valores. Fácil
- Mínimo Múltiplo Comum Encontre o menor número positivo divisível por ambos os valores. Fácil
- Aritmética Exata de Frações Realize operações com frações e retorne uma fração reduzida. Médio