1 求最大公约数的经典方法

我们上学的时候都求过最大公约数，大概是小学 5 年级问题，但是我们好像没有在哪个计算器上直接找到求最大公约数的按键，有时候两个数字很大， 求起来还是挺麻烦的，但如果借助电脑这件事就容易了，今天我们一起在电脑上用小学一年级同学也会使用的Scratch软件编程帮我们实现自动求最大公约数的功能。

先回顾一下求最大公约数的数学逻辑。求最大公约数是数学中的一个经典问题，数学家们想出来很多种方法，其中最早的一种方法叫辗转相除法，出现在距今 2300 多年前的古希腊数学家欧几里得所著的《几何原本》一书中，所以也被称为欧几里得算法，它是目前仍然在使用的算法之一。下面我们就一起来看一下这个算法。

题目：A、B有最大公约数K，并且A > B，已知A, B来求K。

用辗转相除法求K的过程：

如果A÷B能除尽，那么B就是两数最大公约数，否则先求A÷B的余数C(C也是K的倍数)。B和余数C最大公约数也是 K ，并且B>C（和题目一样了哦）。把B赋值给A, C赋值给B, 继续第一步，直到能被除尽，此时除数B就是两数的最大公约数。

---

2 推导过程

举两个例子：

1. 12和9两个数求最大公约数。

12÷9=1......39÷3=3.....0所以12和9的最大公约数就是3，注意这个3是第二步除数上的3，而不是商3，求最大公约数时每一步的商是没有用的。

2. 5767和4453两个数求最大公约数。

5767÷4453=1......13144453÷1314=3......5111314÷511=2......292511÷292=1......219292÷219=1......73219÷73=3......0所以5767和4453两个数的最大公约数是73。

说白了辗转相除法求最大公约数就是：不断求两数相除的余数，用除数代替被除数，余数代替除数，直到余数为0，此刻的除数就是最大公约数。

---

3 编程实现

知道辗转相除法的原理，程序就很容易编出来了（如下图），比单纯学数学好的地方是，不管多大的数，会编程序的同学随时都可以求着玩，分分钟出答案。

其实用辗转相除法不但可以求最大公约数，只要稍微变化一下，还可以将10进制转化成2进制。后面我们会继续写文章来看看这个神奇的辗转相除法如何对进制进行转化。