Com vista a tentar resolver o exercício Nº2, andei a procura de uma forma eficaz de encontrar o máximo divisor comum de números.

Apesar de haver várias formas de resolver o problema, penso que a forma mais eficaz será recorrer ao Algoritmo de Euclides, que não é mais do que um método simplificado de encontrar o máximo divisor comum entre dois números inteiros diferentes de zero.

O algoritmo de Euclides é um dos algoritmos mais antigos conhecidos, além disso a implementação do algoritmo não exige qualquer factorização dos valores. O Máximo Divisor Comum entre dois números inteiros resume-se ao maior número inteiro que divide ambos e que tenha resto zero. O Algoritmo de Euclides é baseado no princípio de que o Máximo Divisor Comum não muda se o menor número for subtraído ao maior.

A implementação do Algoritmo pode ser feita da seguinte forma como demonstra o pseudo-código.

AlgoritmoDeEuclides(a: inteiro; b: inteiro): inteiro
variáveis
divisor: inteiro
dividendo: inteiro
c: inteiro

início
dividendo ← a
divisor ← b
enquanto resto(dividendo/divisor) ≠ 0

início
c ← resto(dividendo/divisor)
dividendo ← divisor
divisor ← c
fim-enquanto

AlgoritmoDeEuclides ← divisor
fim-função

Após ter pesquisado acerca da forma como poderei resolver o exercício Nº2, vou então tentar converter o pseudo-código em código C++ que resolva eficientemente o problema.