求最大公因数

最大公因数，又称最大公约数，是指两个或多个整数共有约数中最大的一个。计算最大公因数有多种方法，其中最常见的方法是欧几里得算法，也叫辗转相除法。下面将介绍欧几里得算法的步骤：

1. 输入两个整数$a$和$b$，其中$a>b$。

2. 用$b$去除以$a$，并记商为$q$，余数为$r$。

3. 判断$r$是否为0，若为0，则$a$即为最大公因数；若不为0，则执行下一步。

4. 用原来的$b$除以$r$，并记商为$q'$，余数为$r'$。

5. 如果$r'$不为0，则重复步骤4，直到$r'$为0为止。此时，$b$即为最大公因数。

例如，假设要求出30和45的最大公因数，按照欧几里得算法，步骤如下：

1. 输入两个整数30和45。

2. 用45去除以30，商为1，余数为15。

3. 用30去除以15，商为2，余数为0。因为余数为0，所以30即为最大公因数。

因此，30和45的最大公因数为30。

总之，欧几里得算法是一种简单而有效的求最大公因数的方法，可用于任意两个整数的求解。