ユークリッドアルゴリズム実装

ユークリッドアルゴリズムは,2つの正の整数の最大公約数を計算するために用いられる.原理はaとbの公約数(a>b)がbとmod(a,b)の公約数(mod(a,b)!=0)は、mod(a,b)とmod(b,mod(a,b))の公約数にも等しい.
mod(a,b)==0であれば,bは最大公約数である.もちろん,すべてのbの約数もa,bの約数である.
実装1:
これは非再帰的実現方式である.まずa>bを確保し、a%b!=0であれば、mod(a,b)==0になるまでbとmod(a,b)の残数を計算し、このときbが最大公約数となる.

def gcd(a, b):
    if a < b:
        tmp = b
        b = a
        a = tmp
    while(a % b != 0):
        r = a % b
        a = b
        b = r
    return b


print(gcd(640, 1680))

実装2:
すべてのgcd 2関数の戻り値は、同じ最大公約数を求めるためであるため、それらの戻り値は一致する.結果はいずれも80.

def gcd2(a, b):
    if a < b:
        tmp = b
        b = a
        a = tmp
    if a % b != 0:
        return gcd2(b, a % b)
    else:
        return b


print(gcd2(640, 1680))