Posted on 2013-03-21 09:39
ytl 閱讀(315)
評論(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)