[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)