ex14 欧几里得算法

要学习的知识点

辗转相除法
最大公约数
最小公倍数
余数递推
同时赋值与循环终止

题目

练习 14：用欧几里得算法求两个正整数的最大公约数和最小公倍数。

参考程序：ex14.py；空白练习：lx14.py。

完整代码

以下内容与 ex14.py 一致，可对照右侧讲解阅读。

"""练习 14：用欧几里得算法求两个正整数的最大公约数和最小公倍数。

学习说明：
- 辗转相除法利用性质：gcd(a, b) = gcd(b, a % b)。
- 循环每次把 (a, b) 更新为 (b, 余数)；余数最终变成 0，此时 a 就是最大公约数。
- 先保存原始输入，因为循环会改变 a、b。
- 最小公倍数可用 a*b//gcd；先除再乘可减小中间结果。
"""
a, b = map(int, input().split())
if a <= 0 or b <= 0:
    raise ValueError("请输入两个正整数")

original_a, original_b = a, b
# 每轮用余数替换较大的问题，直到余数为零。
while b != 0:
    a, b = b, a % b

gcd = a
lcm = original_a // gcd * original_b
print("gcd:", gcd)
print("lcm:", lcm)

进阶写法

这版与初学版解决同一道题，使用更精炼的语法或标准库工具。

进阶源码：ex14_adv.py

"""练习 14 进阶版：用 math.gcd 取得最大公约数，再计算最小公倍数。"""
from math import gcd

a, b = map(int, input().split())
if a <= 0 or b <= 0:
    raise ValueError("请输入两个正整数")

greatest_common_divisor = gcd(a, b)
least_common_multiple = a // greatest_common_divisor * b
print("gcd:", greatest_common_divisor)
print("lcm:", least_common_multiple)

math.gcd(a, b) 返回最大公约数；最小公倍数用 a//gcd*b 计算，先除后乘可减小中间数。

运行结果

示例输入：

18 30

程序输出：

gcd: 6
lcm: 90

逐个认识函数

下表根据程序中实际调用的函数和方法整理；自定义函数的实现与算法细节见后续说明。

函数形式	功能与返回值	注意事项
`ValueError(message)`	内置异常类型，用来表示参数值不符合要求。	raise ValueError(...) 会立即抛错并停止当前程序流程。
`input(prompt='')`	读取一行文本，返回 str；若提供 prompt 会先显示提示。	返回值默认是字符串，计算前通常要做类型转换。
`str.split(sep=None)`	按分隔符拆分字符串，返回字符串列表。	默认按连续空白拆分并忽略首尾空白。
`map(function, iterable)`	逐个应用函数，返回惰性迭代器。	常与 list() 一起使用以立即取得结果。
`print(*objects, sep=' ', end='\n')`	把对象转换为文本显示；返回 None。	默认空格分隔并在末尾换行。

欧几里得算法原理

设 a 大于 b。若一个数同时整除 a 和 b，它也整除 a-b；更一般地，a 除以 b 的余数不会改变最大公约数：gcd(a,b) = gcd(b,a%b)。不断用“除数、余数”替换这一对数，余数为 0 时，当前除数就是 gcd。

从输入两个正整数开始。
记住原数，因为后续循环会改变 a、b。
只要 b 不为 0，就同时令 a=b、b=a%b。
循环结束时 a 是 gcd。根据 lcm(a,b)=a*b/gcd(a,b) 求 lcm。

代码里的函数和语法

写法	功能 / 返回值	易错点
`input().split()`	读一行并按空白拆分，得到字符串列表。	输入两个数时要提供两个项目。
`map(int, ...)`	逐项把字符串变整数，返回 map 对象。	配合多重赋值取得 a、b。
`a, b = b, a % b`	先计算右边的两个值，再一起赋给左边变量。	不会先覆盖旧 a；这是欧几里得循环的关键。
`while 条件:`	条件为真时重复执行代码块。	余数会变小，最终达到 0，保证停止。
`raise ValueError(text)`	抛出输入值错误，程序异常结束。	本题只接受正整数，避免除数为 0 和无定义的 lcm。

最小公倍数为什么这样算

两个正整数的乘积等于它们的最大公约数乘最小公倍数：a*b = gcd*lcm，所以 lcm 可写作 a//gcd*b。先除后乘可减少中间数的大小。gcd 非零，因为本题输入都是正整数。

跟踪循环时写出每轮的 a、b、a%b 三列，尤其注意右侧值使用旧的 a 和 b。

代码如何运行

先按左侧题目给出的格式输入数据；程序通过 input() 读取，并在需要时转换数据类型。
程序自上而下执行语句；遇到条件、循环或函数调用时，按照右侧算法说明更新变量和处理数据。
最后由 print() 输出计算结果。可将左侧示例输入与输出逐项对照。

先自己跟踪一组小数据，记录循环前后变量的值；这比只看最终答案更容易理解程序。

自己动手试一试

测试两个数相同、一个数是另一个数倍数，以及较大的互质数。

先在 lx14.py 中独立完成，再运行参考程序比较结果。修改程序时一次只改一个条件或步骤。