欧几里得算法（GCD）可视化工具
以动画形式演示欧几里得算法——通过不断将 (a, b) 替换为 (b, a mod b)，逐步计算两个数的最大公约数。直接在浏览器中运行。
伪代码
Run an operation to see its steps.
Avg · Worst
使用方法
- 1 输入两个用逗号分隔的数字（例如：48, 36），然后点击「计算 GCD」。
- 2 观察每一步将 (a, b) 替换为 (b, a mod b) 的过程，直到 b 变为 0。
- 3 当 b 变为 0 时，a 就是最大公约数。
- 4 点击「随机」获取一组新的数字，或逐步执行每一次除法运算。
为什么使用此工具
- 亲眼见证欧几里得算法——数学史上最古老的算法之一——的实际运行过程。
- 理解为什么 gcd(a, b) = gcd(b, a mod b)，以及为什么这个算法能如此迅速地结束。
- 观察数值以对数级别快速递减，直到其中一个数归零。
- 完全在浏览器中运行，无需注册，也不会上传任何数据。
常见问题
什么是欧几里得算法？
一种求两个整数最大公约数（GCD）的方法：不断用较大数除以较小数所得的余数替换较大数，直到余数为 0 为止。
欧几里得算法的时间复杂度是多少？
O(log min(a, b))——运算步数与数字的位数成正比，这正是它即使面对非常大的数字也能极快求解的原因。
为什么 gcd(a, b) = gcd(b, a mod b)？
a 和 b 的任何公约数也必然能整除 a mod b（反之亦然），因此这种替换不会改变公约数的集合——自然也就不会改变最大公约数。
GCD 有哪些用途？
用于约分分数、模运算、扩展欧几里得算法（模逆元、RSA 加密），以及通过公式 lcm(a,b) = a·b / gcd(a,b) 计算最小公倍数。
什么是 欧几里得算法（GCD）可视化工具？
欧几里得算法可视化工具演示了如何通过不断用 (b, a mod b) 替换数对 (a, b)，直到 b 变为 0 来求出两个整数的最大公约数——此时 a 就是最大公约数。
功能特性
逐步动画演示
观察每一步除法与取余运算,直到余数变为 0。
复杂度
时间复杂度:O(log min(a, b)) 次除法运算。空间复杂度:O(1)。
100% 隐私保护
完全在浏览器中运行——不会上传任何数据。
示例
Input
gcd(48, 18)Output
48 = 2·18 + 12; 18 = 1·12 + 6; 12 = 2·6 + 0 → GCD = 6常见使用场景
-
1
化简分数
使用最大公约数(GCD)将分数化简为最简形式。
-
2
理解算法原理
了解余数为何能快速缩小,从而产生对数级的步骤数。
-
3
数论基础
学习模运算和 RSA 算法的基础知识。
Zerethon 的欧几里得算法可视化工具会在浏览器中动态演示求两个整数最大公约数的过程:不断用较大数除以较小数所得的余数替换较大数,直到余数为 0。该算法只需 O(log min(a, b)) 次除法运算,空间复杂度为 O(1)——它是至今仍在使用的最古老的算法之一(欧几里得《几何原本》,约公元前 300 年)。
- 分类
- 算法
- 价格
- 免费
- 隐私
- 基于浏览器
- 注册
- 无需
参考资料
- 欧几里得算法 — Wolfram MathWorld — Wolfram MathWorld
- 欧几里得算法 — Wikipedia
隐私
除非另有说明，否则你的数据永远不会离开浏览器。欧几里得算法（GCD）可视化工具 完全在客户端运行 — 无需上传服务器，不记录日志，不追踪你输入的内容。
刚接触？阅读包含 Big-O 分析的分步讲解： 了解 Number Theory →
在 Zerethon Social 上创作、分享与成长
免费注册。赚取积分，收集成就，与全球创作者建立联系。