如何用辗转相除法求最大公约数？

辗转相除法，也称欧几里得算法，是求两个正整数a和b的最大公约数的一种方法。其基本思想是：用较小的数除较大的数，再用现的余数去除除数，直到余数为零时，最后的除数即为这两个数的最大公约数。具体步骤如下：

1.设两个正整数为a和b（a>b）；
2.用a除以b，得到余数r1；
3.用b除以r1，得到余数r2；
4.用r1除以r2，得到余数r3；
5.重复上述步骤，直到余数为0为止，此时的除数即为a和b的最大公约数。

以下是用Python实现辗转相除法求最大公约数的代码：

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

其中，a和b分别为两个正整数，函数返回值为它们的最大公约数。

相关问题

c语言用辗转相除法求最大公约数

以下是使用辗转相除法在C语言中求最大公约数的代码和解释：

#include <stdio.h>

int gcd(int a, int b) {
    int c = a % b;
    while (c) {
        a = b;
        b = c        c = a % b;
    }
    return b;
}

int main() {
    int m, n;
    scanf("%d%d", &m, &n);
    int ret = gcd(m, n);
    printf("%d\n", ret);
    return 0;
}

代码解释：

1. 首先定义了一个名为`gcd`的函数，该函数接受两个整数参数`a`和`b`，返回它们的最大公约数。

2. 在函数中，定义了一个变量`c`，用于存储`a`除以`b`的余数。

3. 使用`while`循环，当`c`不为0时，执行以下操作：

a. 将`b`的值赋给`a`，将`c`的值赋给`b`，更新被除数和除数。

b. 计算新的`c`的值，即`a`除以`b`的余数。

4. 当`c`为0时，`b`的值即为`a`和`b`的最大公约数，将其返回。

5. 在`main`函数中，首先读入两个整数`m`和`n`。

6. 调用`gcd`函数，将`m`和`n`作为参数传入，得到它们的最大公约数。

7. 将最大公约数打印输出。

C语言用辗转相除法求最大公约数

在C语言中，可以使用辗转相除法来求两个数的最大公约数。具体步骤如下：
1. 输入两个数a和b。
2. 判断a和b是否都不为0，如果是则继续，否则输出错误信息。
3. 如果a小于b，则交换a和b的值。
4. 用a除以b，得到余数c。
5. 如果c为0，则b就是最大公约数。
6. 如果c不为0，则用b除以c，得到余数d。
7. 重复步骤5和6，直到余数为0，此时b就是最大公约数。
8. 输出最大公约数b。

下面是C语言代码的实现：

#include <stdio.h>
int main() {
    int a, b, c, temp;
    printf("Please input two numbers:");
    scanf("%d %d", &a, &b);
    if (a && b != 0) {
        if (a < b) {
            temp = a;
            a = b;
            b = temp;
        }
        c = a % b;
        while (c != 0) {
            a = b;
            b = c;
            c = a % b;
        }
        printf("%d", b);
    } else {
        printf("Error");
    }
}