动画笔记中如何用辗转相除法求最大公约数和最小公倍数？

本文共计791个文字，预计阅读时间需要4分钟。

最近学起了C语言，尝试着结合最近学的运算法则写了个计算工具，遇到了一个需求：分数的约分。分数约分怎么一步步到位呢？答案简便的是：找分子和分母的最大公约数。那么怎么最快呢？

最近咱摸起了C语言，尝试着结合最近学的运筹学写个计算工具，途中遇到了一个需求：分数的约分。

• 分数约分怎样一步到位呢？答案便是找分母和分子的最大公约数。

• 那么怎么尽快算出最大公约数呢？网上查了一查，发现了一个算法：辗转相除法。

  

这篇笔记就简单而直观地记录一下这个算法。

最大公约数

这个词非常贴近分数中约分的方法，所谓最大公约数即是多个整数共有的约数中最大的一个，在约分的时候分子和分母同时除以最大公约数，能得到最简分数。

因为上面说的过程中进行的都是整除运算，所以最大公约数也称为最大公因数。

不妨说得更直接一点，公因数就是公约数。