Algoritmo Euclidiano em Python

O Algoritmo Euclidiano, também conhecido como Algoritmo de Euclides, é um algoritmo para determinar o Máximo Divisor Comum(MDC) de dois elementos ou um conjunto de elementos de um mesmo domínio.

Apresentado na obra Elementos de Euclides é um dos algoritmos mais antigos conhecidos datando antes dos gregos antigos. Embora o algoritmo tenha recebido nome de Euclides, provavelmente, ele foi descoberto 200 anos antes.

A técnica do Algoritmo de Euclides consiste em divisões sucessivas para determinação do MDC. Como todo número possui um conjunto finito de divisores, o MDC consiste em saber o maior divisor dentre esse conjunto.

Exemplo: mdc( 480, 130 )

Temos:
480 = 130.3 + 90 (resto é 90)
130 = 90.1 + 40 ( resto é 40)
90 = 40.2 + 10 ( resto é 10)
40 = 10.4 + 0

Logo, mdc(480, 130) = 10

Note que são feitas divisões sucessivas entre a e b até que se obtenha 0 como resto da divisão. A cada iteração efetuada, o denominador da equação anterior se torna o numerador da próxima equação e o resto torna-se o denominador do novo MDC.

	3	1	4	10
480	130	90	10	0
130	90	40	10

Uma das funcionalidades do Algoritmo de Euclidiano é sua utilização em Criptografia.

Criptografia é estudo de métodos para codificar uma mensagem de modo que somente o seu legítmo destinátario consiga entendê-la.

Código em Python

#!/usr/bin/env python

#
# AUTHOR: Jose Mauro da Silva Sandy - http://informacaocomdiversao.blogspot.com
#
# CONTACT: jmsandy _at_ gmail _dot_ com
#
# DATE: 2008-10-19
#
# More information about Euclidean algorithm, visit:
# http://en.wikipedia.org/wiki/Euclidean_algorithm
###############################################################################

def search_gcd(a, b):  
   """ Searching de Greatest Common Divisor """

   if(a != 0):                  
       while(b != 0):           
           if(a > b):
               a = a - b               

           else:
               b = b - a  

   return a         

print "GCD - Greatest Common Divisor\n"

gcd = search_gcd(int(raw_input("Enter with the first element: ")),
                int(raw_input("Enter with the first element: ")))

print "The Greatest Common Divisor is " + str(gcd)

José Mauro da Silva Sandy