Thursday, 22 September 2016

Greatest common divisor using iterative method

Another day, another python lesson on MITx.

This algorithm receive two integers and output the greatest common divisor of the integers.
It is implemented using iterative method.

Notice for future me: use and instead of the bitwise operator &.


def gcdIter(a, b):
    '''
    a, b: positive integers
    
    returns: a positive integer, the greatest common divisor of a & b.
    ''' 
    
    if(a>b):
        tmp=b
        while tmp>0:
            if (a%tmp==0 and b%tmp==0):
                return tmp
            else:
                tmp-=1        
        
    elif(b>a):
        tmp=a
        while tmp>0: 
            if (a%tmp==0 and b%tmp==0):
               return tmp
            else:
                tmp-=1


Shoutout to http://hilite.me/ for the source code formatting! Nifty little tool I will save for future usage.

No comments:

Post a Comment