辗转相除法求两个整数的最大公约数

辗转相除法（欧几里得算法）求两个整数的最大公约数的步骤如下：

1. 用较大的数除以较小的数，得到商和余数，记为a=q×b+r。

2. 若余数r为0，则b即为两数的最大公约数。

3. 若余数r不为0，则用较小的数b除以余数r，得到商和余数，记为b=r×q1+r1。

4. 若余数r1为0，则r即为两数的最大公约数。

5. 若余数r1不为0，则继续用较小的数r除以余数r1，得到商和余数，记为r1=r×q2+r2。

6. 如此下去，直到余数为0为止，最后一个余数即为两数的最大公约数。

例如，求36和24的最大公约数：

36÷24=1······12

24÷12=2······0

所以，36和24的最大公约数为12。

相关问题

用辗转相除法求两个整数公约数

辗转相除法，也叫欧几里得算法，是求最大公约数的一种常用方法。

假设要求两个正整数a和b的最大公约数，用辗转相除法的步骤如下：

1. 用a除以b，得到商q和余数r；
2. 如果r等于0，则b就是最大公约数；
3. 如果r不等于0，则用b除以r，得到商q'和余数r'；
4. 如此反复，直到余数为0，则最后一个非零余数的除数就是a和b的最大公约数。

以下是辗转相除法的Python代码实现：

def gcd(a, b):
    while b != 0:
        r = a % b
        a = b
        b = r
    return a

其中，a代表第一个整数，b代表第二个整数。

用辗转相除法求两个整数的最大公约数

以下是使用辗转相除法求两个整数的最大公约数的Python代码：

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

# 示例
print(gcd(24, 36)) # 输出：12

在这个代码中，我们定义了一个名为`gcd`的函数，它接受两个整数`a`和`b`作为参数。如果`b`等于0，则返回`a`，否则递归调用`gcd`函数，将`b`和`a%b`作为参数传递给它。这个过程会一直持续到`b`等于0，此时`a`就是最大公约数。