Source

CCP2011 / MDC.py

# -*- coding: utf-8 -*-
"""
Máximo Divisor Comum: O algoritmo de euclides e variantes
Created on Thu Jun 16 11:11:53 2011

@author: Flávio Codeço Coelho<fccoelho@gmail.com>
"""
# Por decomposição em fatores primos
import time

def timeit(fun):
    """
    Decorador para calcular o tempo usado por funções (ou métodos)
    """
    def timed(*args, **kw):
        ts = time.time()
        result = fun(*args, **kw)
        te = time.time()
        print '%r (%s,%s)  %2.2f sec'%(fun.__name__, args, kw , te-ts)
        return result
    return timed

def MDC_forca_bruta(a,b):
    """
    testa inteiros em ordem decrescente
    """
    if a == 0 or b == 0:
        return a or b
    for i in xrange(min(a,b),0,-1):
        if not (a%i or b%i):
            return i

def MDC_E(a,b):
    """
    Algoritmo de Euclides
    Versão recursiva
    """
    if b == 0:
        return a
    return MDC_E(b,a%b)
    
def MDC_E_l(a,b):
    """
    Algoritmo de Euclides
    sem recursão
    """
    while b != 0:
        b,a = a%b,b
    return a
    
if __name__=="__main__":
    print MDC_forca_bruta(3426543,6737265)
    print MDC_E(3426543,6737265)
    print MDC_E_l(3426543,6737265)