从算法到实现：如何高效求解最大公约数与最小公倍数

1次阅读

共计 1275 个字符，预计需要花费 4 分钟才能阅读完成。

在编程中，最大公约数（GCD）和最小公倍数（LCM）是常见的数学计算需求，尤其在处理分数运算、加密算法、时间调度等问题时尤为重要。然而，手动计算这些值不仅低效，而且容易出错。传统的暴力枚举法虽然直观，但对于大数计算来说效率极低。因此，我们需要一种高效的算法来解决这一问题。

常见的 GCD 算法有两种：暴力枚举法和欧几里得算法。

暴力枚举法：从两个数中较小的数开始，逐个递减测试是否能同时整除两个数。这种方法的时间复杂度为 O(min(a, b))，对于大数来说效率极低。
欧几里得算法：基于数学原理，通过递归或迭代的方式快速收敛到 GCD。其时间复杂度为 O(log(min(a, b)))，效率显著高于暴力枚举法。

显然，欧几里得算法是更优的选择。

以下是 Python 实现的欧几里得算法，用于计算两个整数的 GCD：

def gcd(a, b):
    """
    计算两个整数的最大公约数（GCD）:param a: 第一个整数
    :param b: 第二个整数
    :return: a 和 b 的最大公约数
    """
    while b != 0:
        a, b = b, a % b
    return a

函数 gcd 接受两个参数 a 和b。
通过循环不断将 b 赋值给 a，并将a % b 赋值给 b，直到b 为 0。
此时 a 即为 GCD。

LCM 可以通过 GCD 快速计算，公式为：

LCM(a, b) = |a * b| / GCD(a, b)

以下是 Python 实现的 LCM 计算：

def lcm(a, b):
    """
    计算两个整数的最小公倍数（LCM）:param a: 第一个整数
    :param b: 第二个整数
    :return: a 和 b 的最小公倍数
    """
    return abs(a * b) // gcd(a, b)

函数 lcm 调用 gcd 函数计算 GCD。
使用公式 |a * b| / GCD(a, b) 计算 LCM。
使用 abs 确保结果为非负数，//确保结果为整数。

欧几里得算法的时间复杂度为 O(log(min(a, b)))，这意味着即使对于非常大的数，算法也能快速收敛。相比之下，暴力枚举法的时间复杂度为 O(min(a, b))，效率明显较低。

在实际应用中，可能会遇到以下问题：

负数处理：GCD 和 LCM 通常定义为非负数，因此在计算前应对输入取绝对值。
零值判断：如果其中一个数为 0，GCD 为另一个数的绝对值，而 LCM 为 0。

改进后的代码：

def gcd(a, b):
    a, b = abs(a), abs(b)
    while b != 0:
        a, b = b, a % b
    return a

def lcm(a, b):
    a, b = abs(a), abs(b)
    if a == 0 or b == 0:
        return 0
    return (a * b) // gcd(a, b)