你已经掌握了基本数学原理（2300多年前的数学问题）

在人教版小学五年级数学课本里，讲到了最大公因数的概念：

为了帮助儿子更容易理解这个概念，我打算用编程的方法来讲解。首先，我用一道题目引入：

假如你有一根长12米的铁丝和一根长9米的铁丝，要把它们截成同样长的小段，要求没有剩余，请问，每段最长是几米？

其实，我出的这道题是数学上的经典问题之一，其本质就是求两数的最大公因数。

学习数学题，抽象思维很重要。因此，求最大公因数的问题可以转换为以下描述：

假设有两个自然数A和B，且A > B，它们的最大公因数是K。已知A, B，求K。

历史上的数学家们对于这个问题曾经想出了很多不同的解法。早在距今 2300 多年前的古希腊，数学家欧几里得在所著的《几何原本》一书中就提出了一种方法：辗转相除法，也叫欧几里得算法。

欧几里德《几何原本》

辗转相除法的思路是这样的：

第一步，先用大数除以小数，即A÷B，看是否能整除。如果是，那么B就是两数的最大公因数，否则求余数，记为C。

第二步：把B赋值给A, C赋值给B。继续上一步的步骤，即A÷B，如果能整除，那么此时的B就是两数的最大公因数。否则，继续以上步骤，直到能整除时，此时的除数B就是两数的最大公约数。

用一句话概括如下：

不断求两数相除的余数，用除数代替被除数，余数代替除数，直到余数为0，此时的除数就是最大公约数。

听起来很简单对不对？下面我们就来验证一下：

先来看看上面那道题目 ，其实就是求12和9的最大公因数。

1. 12÷9=1......3
2. 9÷3=3.....0

上面那道题里的12和9都比较小，因此只需要进行两次计算就得出了答案：12和9的最大公因数是3。

那么，如果是两个较大的数呢？

求767和4453的最大公因数。其实多大的数都没关系，方法还是一样：

1. 5767÷4453=1......1314
2. 4453÷1314=3......511
3. 1314÷511=2......292
4. 511÷292=1......219
5. 292÷219=1......73
6. 219÷73=3......0

经过了6次计算，得到一个整除的算式：219÷73=3，此时的除数73就是两数的最大公因数。

在信息学奥赛（National Olympiad in Informatics, 简称NOI）中，也会涉及到辗转相除法。

在以上的计算中，我们已经知道了辗转相除法的原理，接下来我们用程序来实现。

先画个程序流程图

然后在scratch实现：

借助编程的方法学习数学，可以让孩子很直观地验证自己的思路，也能增加趣味性，提升孩子学习数学 的兴趣。让孩子试着输入任意数字，验证一下答案吧：