Ytl's Java Blog

厚积而薄发---每一天都是一个全新的开始
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

最大公约数

Posted on 2013-03-21 09:39 ytl 阅读(185) 评论(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)

只有注册用户登录后才能发表评论。


网站导航: