Python 最大公约数 最小公倍数

基础概念：

a / b = c ......0  ，则a是b的倍数，b是a的因数（又称“约数”）。

公倍数：两个或多个整数公有的倍数叫做它们的公倍数，其中除0以外最小的一个公倍数就叫做这几个整数的最小公倍数。 整数a，b的最小公倍数记为[a，b]，同样的，a，b，c的最小公倍数记为[a，b，c]，多个整数的最小公倍数也有同样的记号。

公约数：亦称“公因数”。它是一个能被若干个整数同时均整除的整数。如果一个整数同时是几个整数的约数，称这个整数为它们的“公约数”； 公约数中最大的称为最大公约数。对任意的若干个正整数，1总是它们的公因数。a、b的公约数记为(a, b)。

合数：除了1和它本身外，还有其他正因数。

质数：在大于1的自然数中，除了1和本身外，不能被其他自然数整除，即没有其他正因数。

1的正因数只有1，所以它非质数非合数。

a是b的因数，且a是质数，则a是b的质因数；如2,3,5是30的质因数，而6不是。

公因数只有1的两个非0自然数，为互质数。比如3和10。

两个自然数的最大公约数与它们的最小公倍数的乘积等于这两个数的乘积。

一. 最大公约数（gcd）

如果计算多个数的最大公约数，则先计算其中两个数的gcd，再进而计算所得最大公约数与另一个数之间的最大公约数，直到把所有数计算完，所得的gcd就是它们的最大公约数。

使用辗转相除法计算最大公约数：

def gcd(a, b):
    """
    greatest common divisor，计算两个数的最大公约数。
    使用辗转相除法：初始用a 模 b得到其余数，然后不断地用除数再去 模 余数，直到余数等于除数，
                   所得的余数即为最大公约数
    """
    c = a % b
    if c == 0:
        return b
    return gcd(b, c)

print(gcd(100, 155))
           

使用更相减损法计算最大公约数： 

def moreloss(a, b):
    """定义更相减损，注意，a>=b"""
    a, b = max(a, b), min(a, b)
    c = a - b
    if c == b:
        return b
    return moreloss(b, c)

def gcd_sub(a, b):
    """
    使用“更相减损法”计算最大公约数
    首先判断a和b是否都是偶数，若是，则分别除2，若还都是偶数，则继续除2，直到二者中有一个为奇数为止。
    其次，用a减去b，得到其差，判断 差 与 减数 是否相等，若否，则继续用减数 减去 差，直到满足减数与差相等。
    最后，将第一步除的所有次数的2相乘，再乘以最后的差，即为最大公约数。
 
    """
    even = lambda x, y: (x % 2 + y % 2)
    gcd = 1
    while even(a, b) == 0:
        a, b = a // 2, b // 2
        gcd *= 2
    c = moreloss(a, b)
    return gcd * c

print(gcd_sub(260, 104))
           

质因数分解法：

def gcd_1(a, b):
    """质因数分解"""
    p = 1
    i = 2
    while i <= min(a, b):
        if a % i == 0 and b % i == 0:
            p *= i
            a, b = a // i, b // i
        else:
            i += 1
    return p
print(gcd_1(108, 96))


# 若是计算多个数的最大公约数
b = [12, 30, 50]
f = b[0]
for i in b:
    f = gcd_1(f, i)
print(f)
           

 二. 最小公倍数（lcm）

若是求多个自然数的lcm，则先计算其中两个数的lcm，再计算该lcm与第三个数的lcm，依次执行，直到计算完最后一个数，所得lcm就是它们的最小公倍数lcm。

使用两数乘积除以两数最大公约数得到最小公倍数：

def gcd(a, b):
    """
    greatest common divisor，计算两个数的最大公约数。
    使用辗转相除法：初始用a 模 b得到其余数，然后不断地用除数再去 模 余数，直到余数等于除数，所得的余数即为最大公约数
    """
    c = a % b
    if c == 0:
        return b
    return gcd(b, c)

def lcm(a, b):
    """
    least common multiple，最小公倍数，由于两数的最小公倍数与最大公约数的乘积等于两数的乘积，
    所以先计算两数的最大公约数，然后用两数乘积除以最大公约数，得到就是最小公倍数。
    """
    return a * b // gcd(a, b)
print(lcm(45, 30))
           

质因数分解法：

def lcm(a, b):
    """质因数分解"""
    p = 1
    i = 2
    while i <= min(a, b):
        if a % i == 0 and b % i == 0:
            p *= i
            a, b = a // i, b // i
        else:
            i += 1
    p = p * a * b
    return p
print(lcm(45, 30))


# 若是计算多个数的最小公倍数
a = [12, 30, 50]
s = a[0]
for i in a:
    s = lcm(s, i)
print(s)
           

参考：[1] https://baike.baidu.com/item/%E6%9C%80%E5%A4%A7%E5%85%AC%E7%BA%A6%E6%95%B0

           [2] https://baike.baidu.com/item/%E6%9C%80%E5%B0%8F%E5%85%AC%E5%80%8D%E6%95%B0