Algoritmo de Euclides
Origem: Wikipédia, a enciclopédia livre.
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 12(ln2)π2)lnn.
Índice |
[editar] O algoritmo
Abaixo segue o algoritmo de Euclides em pseudocódigo.
AlgoritmoDeEuclides(inteiro a, inteiro b)
dividendo ← a
divisor ← b
enquanto resto(dividendo/divisor) ≠ 0
c ← resto(dividendo/divisor)
dividendo ← divisor
divisor ← c
retornar divisor
[editar] Exemplo
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.
[editar] Implementação em C/C++
int mdc(int a, int b) {
if (b == 0)
return a;
else
return mdc(b, a % b);
}
[editar] Implementação em Haskell
mdc :: Int -> Int -> Int
mdc a b
| (b == 0) = a
| otherwise = mdc b (mod a b)
