Posted on 2013-03-21 09:39
ytl 阅读(295)
评论(0) 编辑 收藏 所属分类:
学习总结
欧几里德算法又称辗转相除法 gcd(a,b) = gcd(b,r) ,r= a %b 表示 a,b 余数
证明：
a 可以表示为 a= bk + r 其中 r = a % b
假设 d是 是a,b 一个公约数
则有 d|a d|b , 而r= a- bk
因此 d|r 其中d|a d|b d|r {表示后者能被前者整除，余数为0(a%d=0)}
所以 d 是 (b, r)的公约数 {d不能是(a, a%b)的公约数，如果是那么出现r>=k的情况}
假设 d 是 (b, r)的公约数
则有 d|b , d|r ,而 a= bk+r
因此 d也是(a,b)公约数
所以(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等
Python实现
递归 /迭代
def gcdIter(a, b):
'''
a, b: positive integers
returns: a positive integer, the greatest common divisor of a & b.
'''
if a < b:
a,b = b,a
while b!=0:
a, b = b, a%b
return a
def gcdRecur(a, b):
'''
a, b: positive integers
returns: a positive integer, the greatest common divisor of a & b.
'''
if b == 0:
return a
return gcdRecur(b, a%b)