Posted on 2013-03-21 09:39
ytl 閱讀(321)
評論(0) 編輯 收藏 所屬分類:
學(xué)習(xí)總結(jié)
歐幾里德算法又稱輾轉(zhuǎn)相除法 gcd(a,b) = gcd(b,r) ,r= a %b 表示 a,b 余數(shù)
證明：
a 可以表示為 a= bk + r 其中 r = a % b
假設(shè) d是 是a,b 一個公約數(shù)
則有 d|a d|b , 而r= a- bk
因此 d|r 其中d|a d|b d|r {表示后者能被前者整除，余數(shù)為0(a%d=0)}
所以 d 是 (b, r)的公約數(shù) {d不能是(a, a%b)的公約數(shù)，如果是那么出現(xiàn)r>=k的情況}
假設(shè) d 是 (b, r)的公約數(shù)
則有 d|b , d|r ,而 a= bk+r
因此 d也是(a,b)公約數(shù)
所以(a,b)和(b,a mod b)的公約數(shù)是一樣的，其最大公約數(shù)也必然相等
Python實(shí)現(xiàn)
遞歸 /迭代
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)