Algoritmo de Euclides

O algoritmo de Euclides é um dos mais antigos e famosos que existem. Ele busca encontrar o MDC (Máximo Divisor Comum) entre dois números inteiros. (diferentes de zero). Fez sua primeira aparição no livro sétimo dos Elementos de Euclides por volta do ano 300 a.C.

O processo é também conhecido como método das divisões sucessivas. É bem simples e eficiente pois dispensa fatoração.

A seguir, o algoritmo de Euclides em Pseudocódigo do Visualg: (para ver a versão recursiva do mesmo algoritmo, clique aqui)

algoritmo "algoritmo de Euclides"
// Função : Algoritmo de Euclides
// Autor : Ed
// Data : 12/05/2009
// Seção de Declarações
var
    a,b,c, dividendo, divisor:inteiro
inicio
//entrada de dados
escreval("Algoritmo de Euclides para encontrar o MDC entre 2 números")
escreva("Digite o primeiro numero:")
leia (a)
escreva("Digite o segundo numero:")
leia (b)

//algotimo propriamente dito
dividendo <- a
divisor <- b
enquanto ((dividendo%divisor) <> 0)  faca
     c <- (dividendo%divisor)
     dividendo <- divisor
     divisor <- c
fimenquanto
escreva(divisor)   //apresentacao na tela

fimalgoritmo

Existe também uma versão recursiva, embora a versão apresentada acima seja a versão clássica do Algoritmo.
Clique aqui para conhecer diversas aplicações do MDC em problemas de concursos públicos.

Euclides de Alexandria. Fonte aqui.

Até.