欧几里得算法（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 就是最大公约数。
功能特性
Step-by-step animation
Watch each division-and-remainder step until the remainder hits zero.
Complexity
Time: O(log min(a, b)) division steps. Space: O(1).
100% private
Runs entirely in your browser — nothing is uploaded.
示例
Input
gcd(48, 18)Output
48 = 2·18 + 12; 18 = 1·12 + 6; 12 = 2·6 + 0 → GCD = 6常见使用场景
-
1
Reduce fractions
Use the GCD to simplify a fraction to lowest terms.
-
2
Understand the algorithm
See why remainders shrink quickly, giving logarithmic steps.
-
3
Number theory basics
Learn the foundation for modular arithmetic and RSA.
Zerethon's Euclidean algorithm visualizer animates finding the greatest common divisor of two integers in your browser, repeatedly replacing the larger number with the remainder of dividing it by the smaller until the remainder is zero. It runs in O(log min(a, b)) division steps with O(1) space — one of the oldest algorithms still in use (Euclid's Elements, ~300 BC).
- 分类
- 算法
- 价格
- 免费
- 隐私
- 基于浏览器
- 注册
- 无需
References
- Euclidean Algorithm — Wolfram MathWorld — Wolfram MathWorld
- Euclidean algorithm — Wikipedia
隐私
除非另有说明，否则你的数据永远不会离开浏览器。欧几里得算法（GCD）可视化工具 完全在客户端运行 — 无需上传服务器，不记录日志，不追踪你输入的内容。
刚接触？阅读包含 Big-O 分析的分步讲解： 了解 Number Theory →
对比
相关工具
冒泡排序可视化工具
带动画演示的冒泡排序模拟器，提供单步执行、速度调节、自定义输入数据、实时比较/交换计数器以及伪代码同步高亮。完全在浏览器中运行。
打开工具插入排序可视化工具
动画演示插入排序算法，支持单步执行、速度调节、自定义输入数据，并实时显示比较/写入次数与伪代码高亮。完全在浏览器本地运行。
打开工具选择排序可视化工具
以动画方式演示选择排序（Selection Sort），提供逐步执行、速度调节、自定义输入数据、实时的比较/交换计数器以及伪代码展示。完全在浏览器本地运行。
打开工具归并排序可视化工具
带动画演示的归并排序模拟器，支持单步执行、速度调节、自定义输入数据、实时比较/写入计数器以及伪代码高亮显示。完全在浏览器中运行。
打开工具在 Zerethon Social 上创作、分享与成长
免费注册。赚取积分，收集成就，与全球创作者建立联系。