> For the complete documentation index, see [llms.txt](https://facompetindo.gitbook.io/facompetindo/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://facompetindo.gitbook.io/facompetindo/python/euclides.md).

# Algoritmo de Euclides

## 📚 Introdução

O algoritmo de Euclides é um algoritmo que é usado para calcular o máximo divisor comum, assim como o mínimo múltiplo comum entre dois números inteiros.

## 📈 Máximo divisor comum

O máximo divisor comum entre dois números inteiros é o maior número inteiro que divide ambos os números.

Por exemplo, o máximo divisor comum entre 12 e 18 é 6, pois 6 é o maior número que divide ambos 12 e 18.

Uma solução ingênua para calcular o máximo divisor comum entre dois números seria começar no maior número e seguir decrementando até encontrar um número que divide ambos os números.

```py
def mdc(a, b):
    for i in range(max(a, b), 0, -1):
        if a % i == 0 and b % i == 0:
            return i
```

O código acima funciona, mas é muito lento para números grandes.

O algoritmo de Euclides é muito mais rápido, pois ele utiliza a seguinte propriedade matemática:

> Seja `a` e `b` dois números inteiros, com `a > b`. O máximo divisor comum entre `a` e `b` é igual ao máximo divisor comum entre `b` e `a % b`.

Ou seja, se `a` e `b` são dois números inteiros, com `a > b`, mdc(a,b) = mdc(b, a % b).

Ademais, usando o fato de que mdc(a,0) = a, aplicamos a propriedade anterior várias vezes, até que o segundo número seja 0, nesse momento retornamos a.

Por exemplo, para calcular o mdc entre 12 e 18 usando esse algoritmo, o passo a passo seria:

* mdc(18, 12) = mdc(12, 18 % 12) = mdc(12, 6)
* mdc(6, 12 % 6) = mdc(6, 0) = 6

O código em Python fica:

```py
def euclides(a, b):
    if b == 0:
        return a
    return euclides(b, a % b)
```

## 📉 Mínimo múltiplo comum

O algoritmo de Euclides também pode ser usado para calcular o mínimo múltiplo comum entre dois números inteiros.

O MMC de dois números inteiros é o menor número inteiro que é múltiplo de ambos os números.

Por exemplo, o mínimo múltiplo comum entre 12 e 18 é 36, pois 36 é o menor número que é múltiplo de ambos 12 e 18.

Podemos usar a seguinte propriedade para calcular o mínimo múltiplo comum entre dois números inteiros:

> mmc(a,b) = a \* b / mdc(a,b)

Ou seja, o mínimo múltiplo comum entre dois números inteiros é igual ao produto entre os dois números dividido pelo máximo divisor comum entre eles.

O código em Python fica:

```py
def mmc(a, b):
    return a * b / euclides(a, b)
```

## 🧑‍🏫 Exercícios

* Exercício [2443](https://www.beecrowd.com.br/judge/pt/problems/view/2443) do Beecrowd, que caiu na OBI 2013, esse é um exercício simples para demonstrar o uso do algoritmo de Euclides, com algo que fazemos desde o ensino fundamental, soma de frações!