[Python] 欧几里得算法

欧几里得算法是计算两个整数的最大公约数，把a与b相除，得到余数后，把b赋值给a，余数赋值给b，a与b再相除，. . . 如此反复，即可得到最大公约数gcd。用Python可以作出如下函数：

def gcd (a, b):
  r = a % b
  while r > 0:
    print a, b, r
    a, b, r = b, r, b%r
  return b

也可以用另外一种方式来实现欧几里得算法，如果a能被b整除，那么b就是两数的公约数；如果a不能被b整除，那么有a=qb+r，q是商，r是余数，那么 0 <= r < b，如果一个数能够整除a和b，那么它就能整除b和r，也就是说gcd(a,b)=gcd(b,r)，用递归法来作：

def gcd2 (a, b):
  r = a % b
  while r == 0:
    return b
  else:
    return gcd2 (b, r)