Python第23题：求两个正整数的最大公约数（欧几里得算法）

题目

从标准输入读入两个正整数 a 和 b，使用欧几里得算法（辗转相除法）计算并输出它们的最大公约数（GCD）。

输入格式：一行输入两个正整数 a 和 b，以空格分隔。

输出格式：输出一个整数，表示 a 和 b 的最大公约数，末尾换行。

数据范围与约定：1 ≤ a, b ≤ 10⁹。

思路与算法

1. 欧几里得辗转相除原理
两数的最大公约数等于较小数与取模余数的最大公约数，即 gcd(a, b) = gcd(b, a % b)。

2. Pythonic 迭代更新
使用双变量同时赋值 x, y = y, x % y，循环直到 y == 0 时终止，此时的 x 即为最大公约数。

完整程序

a, b = map(int, input().split())

# 欧几里得辗转相除法求最大公约数
while b != 0:
    a, b = b, a % b

print(a)

运行示例

输入：

48 18

输出：

6