Encontrando o MDC em Go: da força bruta ao Algoritmo de Euclides

Estava fazendo alguns desafios introdutórios com Go e estudando sobre complexidade de algoritmos — BigO. Confesso: entender BigO tem sido desafiador. Apesar de ser um conceito extremamente importante, era, até então, infrequente a sua aparição no meu dia a dia, o que torna a prática ainda mais essencial.

O prompt do exercício era simples e claro:

Criar uma solução para encontrar o Máximo Divisor Comum (MDC) de dois números, sendo que o MDC é o maior número que divide dois números inteiros positivos sem deixar resto.

Como em qualquer problema, há diversas formas de solucionar — algumas mais eficientes que outras, bem como menos complexas cognitivamente.

Exercer a criatividade: fluindo sem filtro e sem ajuda

Primeiramente, antes de procurar soluções prontas, artigos ou ajuda de IA, quis me aventurar por conta própria. Comecei com a ideia mais natural: encontrar todos os divisores de cada número e depois comparar os comuns para descobrir o maior.

Cheguei a essa “pintura abstrata” no nosso quadro:

func EncontrarMDC(num1, num2 int) (int, error) {
 if num1 <= 0 || num2 <= 0 {
  return 0, errors.New("números devem ser maiores que 0")
 }

 divisores1 := encontrarDivisores(num1)
 divisores2 := encontrarDivisores(num2)

 divisoresComuns := []int{}
 for _, divisor1 := range divisores1 {
  for _, divisor2 := range divisores2 {
   if divisor1 == divisor2 {
    divisoresComuns = append(divisoresComuns, divisor1)
   }
  }
 }

 maior := divisoresComuns[0]
 for _, d := range divisoresComuns {
  if d > maior {
   maior = d
  }
 }

 return maior, nil
}

func encontrarDivisores(num int) []int {
 divisores := []int{}
 for i := 1; i <= num; i++ {
  if num%i == 0 {
   divisores = append(divisores, i)
  }
 }
 return divisores
}

Executei a main.go e deu certo. Com isso, fui ao próximo passo do meu workflow de estudos: identificar a complexidade das etapas que criamos com nossas funções.

• Encontrar divisores: O(n) para cada número
• Comparar todos os divisores entre si: *O(n m)**
• Resultado: *O(n m)** no pior caso

Ou seja, uma solução que funciona, mas que escala mal — principalmente se for para lidar com números grandes. Então, a partir dessa constatação, segui ao próximo passo:

Consultar o oráculo (IA) para “pitacos” de melhorias

Claramente, não estava satisfeito com a solução “natural” e “bruta” que criei — muito menos com as implicações que ela geraria em contextos mais exigentes.

Foi aí que, numa das conversas com o amigo Gepeto (no caso, o GitHub Copilot) me deparei com o clássico Algoritmo de Euclides.

A princípio, não entendi nada — por conta do uso da atribuição múltipla do Go que ainda estou me habituando. Mas é interessante como a linguagem permite realizar trocas e mudanças simultâneas de variáveis de modo seguro, sem precisar alocar memória para outras variáveis temporárias.

Bastou contemplar por um tempo e tagarelar em voz alta, que, então, percebi o quanto este algoritmo é elegante, eficiente e se mostra muito prático para esse tipo de problema.

A lógica é simples:

Enquanto num2 for diferente de zero, substituímos num1 por num2 e num2 por num1 % num2. Quando num2 for zero, o MDC será o valor atual de num1.

Deste modo, não há mais a necessidade de comparar os divisores de cada num e podemos focar no que realmente importa: o resto da divisão.

Refatorando, ficamos com o seguinte quadro:

func EncontrarMDC(num1, num2 int) (int, error) {
 if num1 <= 0 || num2 <= 0 {
  return 0, errors.New("ambos os números devem ser maiores que 0")
 }

 for num2 != 0 {
  num1, num2 = num2, num1%num2
 }

 return num1, nil
}

Menos linhas de código, menos aninhamentos e menos complexidade desnecessária. Aliás, a complexidade da nossa função foi de *O(n m) para O(log(min(num1, num2)))**.

Conclusão

Intrigante como um exercício simples aliado à vontade de ir mais a fundo se torna numa contingência de tantos ensinamentos e reforçamentos:

• Como o aprendizado é mais significativo quando temos um workflow de estudos no qual é dada a liberdade criativa de deixar fluir e refletir sob as linhas de código o que temos de constructos, formas de olhar e tatear o problema, bem como esboçar soluções;
• A importância de estudar algoritmos clássicos (como o de Euclides);
• A diferença e impacto que uma escolha “inocente” de abordagem no “aqui-agora” pode ter no ciclo de vida e na performance de uma solução;
• E como o Go é uma linguagem simples, mas poderosa, com recursos que favorecem legibilidade e eficiência.