Artigo original: Euclidian Algorithm: GCD (Greatest Common Divisor) Explained with C++ and Java Examples
Para tratarmos deste assunto, primeiramente, é preciso conhecer a respeito do máximo divisor comum (MDC ou GCD – no inglês, Greatest Common Divisor) e da operação MOD (de módulo).
Máximo divisor comum (MDC ou GCD)
O MDC de dois ou mais números inteiros é o maior número inteiro que divide es números anteriormente mencionados de tal modo que o resto da divisão é zero.
Exemplo:
O MDC de 20 e 30 é 10 (10 é o maior número que divide 20 e 30 com o resto 0)
O MDC de 42, 120, 285 = 3 (3 é o maior número que divide 42, 120 e 285 com o resto 0)
Operação "mod"
O operador de módulo (mod) mostra o resto da divisão quando dividimos dois números inteiros. Escrevemos isso assim:A mod B = R
Isso significa que, ao dividir A e B, temos o resto R. Essa operação difere da operação regular de divisão, que nos dá o quociente.
Exemplo:
7 mod 2 = 1 (Ao dividir 7 por 2 temos o resto 1)
42 mod 7 = 0 (Ao dividir 42 por 7 temos o resto 0)
Tendo entendido os dois conceitos acima, será fácil de entender o algoritmo de Euclides.
Algoritmo de Euclides para o máximo divisor comum (MDC ou GCD)
O algoritmo de Euclides encontra o máximo divisor comum (que chamaremos nos algoritmos de 'GCD') de 2 números.
Você entenderá melhor esse algoritmo ao vê-lo em funcionamento. Supondo que você deseja calcular o GCD de 1220 e de 516, vamos aplicar o algoritmo de Euclides:
Pseudocódigo do algoritmo
Passo 1: suponha que a, b sejam os dois números
Passo 2: a mod b = R
Passo 3: considere que a = b e que b = R
Passo 4: repita os passos 2 e 3 até que a mod b seja maior do que 0
Passo 5: GCD = b
Passo 6: fim
Código em JavaScript para encontrar o GCD:
function gcd(a, b) {
var R;
while ((a % b) > 0) {
R = a % b;
a = b;
b = R;
}
return b;
}
Código em JavaScript para encontrar o GCD usando a recursividade:
function gcd(a, b) {
if (b == 0)
return a;
else
return gcd(b, (a % b));
}
Código em C para encontrar o GCD usando a recursividade:
int gcd(int a, int b)
{
// Tudo pode ser dividido por 0
if (a == 0)
return b;
if (b == 0)
return a;
// Caso de base
if (a == b)
return a;
// a é maior
if (a > b)
return gcd(a-b, b);
return gcd(a, b-a);
}
Código em C++ para encontrar o GCD:
int gcd(int a,int b) {
int R;
while ((a % b) > 0) {
R = a % b;
a = b;
b = R;
}
return b;
}
Código em Python para encontrar o GCD usando recursividade:
def gcd(a, b):
if b == 0:
return a:
else:
return gcd(b, (a % b))
Código em Java para encontrar o GCD usando recursividade:
static int gcd(int a, int b)
{
if(b == 0)
{
return a;
}
return gcd(b, a % b);
}
Você também pode usar o algoritmo de Euclides para encontrar o máximo divisor comum de mais de dois números. Como o GCD é associativo, a operação a seguir também seria válida: GCD(a,b,c) == GCD(GCD(a,b), c)
Calcule o GCD dos dois primeiros número, depois encontre o GCD do resultado e do número seguinte. Exemplo: GCD(203,91,77) == GCD(GCD(203,91),77) == GCD(7, 77) == 7
Você pode encontra o GCD de n números da mesma maneira.
O que é o algoritmo de Euclides estendido?
Esta é uma extensão do algoritmo de Euclides. Ela também calcula os coeficientes x, y, de tal modo que:
ax+by = gcd(a,b)
x e y também são conhecidos como os coeficientes da identidade de Bézout.
Código em C para o algoritmo de Euclides estendido
struct Triplet{
int gcd;
int x;
int y;
};
Triplet gcdExtendedEuclid(int a,int b){
// Case de base
if(b==0){
Triplet myAns;
myAns.gcd = a;
myAns.x = 1;
myAns.y = 0;
return myAns;
}
Triplet smallAns = gcdExtendedEuclid(b,a%b);
// Algoritmo de Euclides estendido
Triplet myAns;
myAns.gcd = smallAns.gcd;
myAns.x = smallAns.y;
myAns.y = (smallAns.x - ((a/b)*(smallAns.y)));
return myAns;
}