首页  |  Linux  |  C/C++  |  网络编程  |  Python   |  Algorithm  |  数据库  |  经验  |   人生 & 随想   |  站内搜索  |  关于

<<< previous

该文已被浏览1336

如何求解GCD与LCM?

2015-07-29

求解GCD(Greatest Common Divisor)

GCD即最大公约数,求解GCD有两种方法,一种是欧几里得的《几何原本》中提到的辗转相除法,另一种即为中国的《九章算术》中提到的更相减损术。

辗转相除法

   两个数a,b,用a除以b, 如果所得余数不等于0,则用上式中的除数除以上式中的余数,然后就是循环执行粗体部分,直到余数为0,则GCD即为最后一个运算式中的除数。示例如下: 求35和20的GCD:
35 % 20 = 15
20 % 15 = 5
15 % 5 = 0
最大公约数即为5 使用程序语言具体实现如下(以Python为例):
def gcd(A,B):
    while B != 0:
        t = B
        B = A % B
        A = t
    return A

更相减损术

   两个数a和b,用二者中较大的数减去较小的数,如果差和减数不相等,则将上式中的差和减数进行相减,规则是用较大的数减去较小的数,接下来是循环执行粗体部分,直到差和减数相等,则GCD即为最后一个运算式中的差或减数。示例如下: 求35和20的GCD:
35 – 20 = 15
20 – 15 = 5
15 – 5 = 10
10 – 5 = 5
最大公约数即为5 使用程序语言具体实现如下(以Python为例):
def gcd(A,B):
    if A == 0:
        return B
    while B != 0:
        if A > B:
            A -= B
        else:
            B -= A
    return A
说明: 更相减损术与辗转相除法相比,通常辗转相除法效率更高。

求解LCM(Least Common Multiple)

LCD即最小公倍数,可按照如下公式求解
GCD(A,B) * LCM(A,B) = A * B


一如既往,如果你对文章中的内容有任何疑问,或者是发现文章中有任何错误,都可以通过下面的地址发邮件告诉我.
E-mail: rytubuntulinux@gmail.com