O algoritmo de Euclides busca encontrar o máximo divisor comum entre dois números inteiros diferentes de zero. É um dos algoritmos mais antigos conhecidos, desde que apareceu na obra Elementos de Euclides por volta de 300 aC. O algoritmo não requer fatoração.

Embora seja um algoritmo bastante simples, a sua análise revela-se um problema bastante complexo. Não se sabe ao certo qual a complexidade esperada deste algoritmo para valores muito grandes de n, mas estima-se que seja aproximadamente

Abaixo segue o algoritmo de Euclides em pseudocódigo.

AlgoritmoDeEuclides(inteiro a, inteiro b)dividendo ? adivisor ? benquanto resto(dividendo/divisor) ? 0c ? resto(dividendo/divisor)dividendo ? divisordivisor ? cretornar divisor

Tomemos os números 348 e 156:

dividendo ? 348
divisor ? 156

resto(348/156) = 36 ? 0

Como o resto não é zero, substituímos o dividendo e o divisor:

dividendo ? 156
divisor ? 36

resto(156/36) = 12 ? 0

Repetimos o passo anterior:

dividendo ? 36
divisor ? 12

resto(36/12) = 0

retornar 12

Portanto, o máximo divisor comum de 348 e 156 é 12.

int mdc(int a, int b) {if (b == 0)return a;else return mdc(b, a % b);}

(define (mdc a b)(if (= b 0)a(mdc b (remainder a b))))

mdc :: Int -> Int -> Intmdc a b| (b == 0) = a| otherwise = mdc b (mod a b)

public int mdc(int a, int b) {if(b == 0)return a;elsereturn mdc(b, a % b);}

Function mdc(a, b)If b = 0 Thenmdc = aElsemdc = mdc(b, a Mod b)End If
End Function

function mdc(a,b:integer):integer
beginif b = 0 then beginresult := aendelseResult := mdc(b, a mod b)
end;

Lembre-se que o comando x mod y retorna o resto da divisão entre x e y