分析一个蓝桥杯Scratch编程竞赛试题《求两个数的最大公约数》。题目要求：输入任意两个非负整数，求它们的最大公约数。
1、分析与解题
最大公约数，也称最大公因数。指两个或多个整数共有的约数中最大的一个。求最大公约数有多种方法，常见的有质因数分解法、短除法、辗转相除法、更相减损法，在我们数学课堂上，我们最常用的是质因数分解法和短除法。质因数分解法：把每个数分别分解质因数，再把各数中的全部公有质因数提取出来连乘，所得的积就是这几个数的最大公约数。例如:求12和54的最大公约数，先分解质因数，得12=2×2×3，54=2×3×3×3，12与45的全部公有的质因数是2、3，它们的积是2×3=6，所以，（12，54）=6。短除法：短除法求最大公约数，先用这几个数的公约数连续去除，一直除到所有的商互质为止，然后把所有的除数连乘起来，所得的积就是这几个数的最大公约数。短除法的本质就是质因数分解法，只是将质因数分解用短除符号来进行。今天我们要用Scratch来解决求最大公约数，我们将采用辗转相除法,即欧几里得算法。这种算法是古希腊数学家欧几里得在其著作《The Elements》中最早描述的,所以被命名为欧几里得算法，在国内也被称为辗转相除法。欧几里得算法具体如下：取两个数中最大的数做除数，较小的数做被除数，用最大的数除较小数，如果余数为0，则较小数为这两个数的最大公约数，如果余数不为0，用较小数除上一步计算出的余数，直到余数为0，则这两个数的最大公约数为上一步的余数。举个例子：假如需要求 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。根据前面介绍的欧几里得算法的具体步骤，我们可以用Scratch进行，具体如下：
首先我们先建立两个变量a和b，同时建立a1和b1用于存放我们输入的两个数。设一个新的变量r，用于存放第一次除法运算下来的余数。同时将b赋给a，将余数赋给b,进行新一轮的除法运算，直到余数等于0即可。
