青少年信息学奥赛算法の辗转相除法

辗转相除法是全国青少年信息学奥利匹克系列竞赛（NOI）大纲中，入门级（CSP-J）要求掌握的知识点，是用来求两个正整数最大公约数的算法，古希腊数学家欧几里得在其著作《The Elements》中最早描述了这种算法，所以也被命名为欧几里得算法：

两个正整数的最大公约数等于其中较小的那个数（也就是除数）和两数相除余数的最大公约数。最大公约数（Greatest Common Divisor）缩写为GCD，计算公式为GCD(a,b)=GCD(b,a mod b)。

假如需要求1997和615两个正整数的最大公约数，用欧几里得算法，是这样进行的：

1997 / 615 = 3(余 152)

615 / 152 = 4(余7)

152 / 7 = 21(余5)

7 / 5 = 1(余2)

5 / 2 = 2(余1)

2 / 1 = 2(余0)

至此，最大公约数为1

以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数，所以就得出了 1997 和 615 的最大公约数 1。

那么，在计算机领域中，我们该如何实现它呢？来看一道蓝桥杯的例题：

创建函数：求两个数字的最大公约数

流程图如下：

流程图

简单来说，现在有a,b两个数，先拿a除以b得到余数c，如果c不等于0的话，就把除数b的值赋给a,把余数c的值赋给b，再拿新的a除以新的b，得到新的c以此类推……如果得到的余数c等于0的话，那么之前的除数b就是最大公约数。你学会了吗？