从算法到实现：用函数求解最大公约数与最小公倍数的完整指南

1次阅读

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

最大公约数（GCD）和最小公倍数（LCM）是数学中的基本概念，在编程中经常用于解决分数化简、时间调度等问题。举个例子：当我们需要把 24/36 约分时，就要找到 24 和 36 的最大公约数 12；当计算两个齿轮同时回到起点位置的周期时，就需要用到最小公倍数。

这个算法的精妙之处在于：两个数的最大公约数，等于较大数减去较小数的差与较小数的最大公约数。重复这个过程直到两数相等，那个数就是最大公约数。

具体步骤：

比较两个数大小
用大数减去小数得到新数
用新数和小数继续比较
重复直到两数相等

例如求 56 和 32 的 GCD：
56-32=24 → 32-24=8 → 24-8=16 → 16-8=8 → 8=8，所以 GCD 是 8

最小公倍数有个巧妙的计算公式：LCM(a,b) = ab/GCD(a,b)。比如 12 和 8 的 GCD 是 4，那么 LCM 就是 128/4=24。

用 Python 实现这两个函数：

def gcd(a, b):
    """计算最大公约数"""
    while b != 0:
        a, b = b, a % b  # 使用取模运算更高效
    return abs(a)  # 保证返回正值

def lcm(a, b):
    """计算最小公倍数"""
    return abs(a * b) // gcd(a, b) if a and b else 0  # 处理除零情况

# 主程序
if __name__ == '__main__':
    num1 = int(input("请输入第一个整数:"))
    num2 = int(input("请输入第二个整数:"))

    print(f"{num1}和 {num2} 的最大公约数是: {gcd(num1, num2)}")
    print(f"{num1}和 {num2} 的最小公倍数是: {lcm(num1, num2)}")

运行示例：

请输入第一个整数: 56
请输入第二个整数: 32
56 和 32 的最大公约数是: 8
56 和 32 的最小公倍数是: 224

负数处理：我们使用 abs()函数保证返回正值
零值处理：当输入有 0 时，LCM 定义为 0
相同数字：直接返回该数字

递归写法更简洁但可能有栈溢出风险：

def gcd_recursive(a, b):
    return a if b == 0 else gcd_recursive(b, a % b)

迭代写法性能更好，推荐在实际项目中使用。

代码可读性：
使用有意义的函数名
添加清晰的注释
处理边界条件

单元测试建议：

import unittest

class TestMathFunctions(unittest.TestCase):
    def test_gcd(self):
        self.assertEqual(gcd(56, 32), 8)
        self.assertEqual(gcd(-15, 10), 5)

    def test_lcm(self):
        self.assertEqual(lcm(12, 8), 24)
        self.assertEqual(lcm(5, 0), 0)

if __name__ == '__main__':
    unittest.main()