给定两个正整数a、b，求它们的最大公约数。 输入描述 两个正整数a、b（1≤a≤103,1≤b≤103）。 输出描述 输出a和b的最大公约数。 C语言回答

可以使用辗转相除法（又称欧几里得算法）求两个正整数的最大公约数。具体步骤如下：

1. 将a、b中较大的数赋值给max，较小的数赋值给min；
2. 用max除以min，得到商q和余数r；
3. 如果r等于0，那么min就是a和b的最大公约数；
4. 否则，将min赋值为r，将max赋值为原来的min，然后返回步骤2。

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

#include <stdio.h>

int gcd(int a, int b) {
    int max = a > b ? a : b;
    int min = a <= b ? a : b;
    while (min != 0) {
        int r = max % min;
        max = min;
        min = r;
    }
    return max;
}

int main() {
    int a, b;
    scanf("%d %d", &a, &b);
    printf("%d\n", gcd(a, b));
    return 0;
}

其中，gcd函数用于求a和b的最大公约数。在while循环中，用max除以min，得到商q和余数r。如果r等于0，那么min就是a和b的最大公约数，直接返回min即可。否则，将min赋值为r，将max赋值为原来的min，继续循环。最后输出最大公约数即可。

相关问题

给定两个正整数，求它们的最大公约数。

最大公约数可以通过计算两个正整数的最大公因数来计算，例如对于12和18，它们的最大公约数为6。
最大公约数可以通过辗转相除法来求得。好的，假设给定两个正整数 a 和 b，我们需要求它们的最大公约数。

最大公约数（Greatest Common Divisor，简称 GCD）是指能够同时整除 a 和 b 的最大正整数。我们可以使用欧几里得算法来求解最大公约数，该算法基于如下的性质：

1. 如果 a 能够整除 b，那么 a 就是 a 和 b 的最大公约数。
2. 如果 a 不能够整除 b，那么 a 和 b 的最大公约数等于 b 和 a mod b 的最大公约数。

按照上述性质，我们可以使用递归的方式求解最大公约数。具体地，如果 b 等于 0，则 a 就是最大公约数；否则，我们将 b 和 a mod b 作为参数递归调用函数，直到 b 等于 0。

下面是该算法的中文实现：

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

接下来，我们可以利用最大公约数求最小公倍数。最小公倍数（Least Common Multiple，简称 LCM）是指能够同时被 a 和 b 整除的最小正整数。根据最小公倍数和最大公约数的关系，我们可以使用如下公式计算最小公倍数：

lcm(a, b) = a * b / gcd(a, b)

因此，我们可以编写以下代码来求解给定两个正整数的最大公约数和最小公倍数：

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

def lcm(a, b):
    return a * b / gcd(a, b)

a = 12
b = 18
print("a 和 b 的最大公约数为：", gcd(a, b))
print("a 和 b 的最小公倍数为：", lcm(a, b))

python给定两个正整数，求它们的最大公约数和最小公倍数

### 回答1：
最大公约数可以使用辗转相除法或欧几里得算法来求解，具体步骤如下：

1. 用较大数除以较小数，得到余数
2. 如果余数为0，则较小数即为最大公约数
3. 如果余数不为0，则用较小数除以余数，得到新的余数
4. 重复步骤2和3，直到余数为0，此时较小数即为最大公约数

最小公倍数可以通过最大公约数来求解，具体公式为：

最小公倍数 = 两数之积 / 最大公约数

例如，给定两个正整数a=12和b=18，求它们的最大公约数和最小公倍数：

1. 用18除以12，得到余数6
2. 用12除以6，得到余数0，此时12即为最大公约数
3. 最小公倍数 = 12 * 18 / 12 = 18

因此，12和18的最大公约数为12，最小公倍数为18。

### 回答2：
求两个正整数的最大公约数和最小公倍数是数学中的基本问题。在Python中，可以使用辗转相除法和最小公倍数公式来求解这个问题。

首先，来介绍辗转相除法。它也叫欧几里德算法，步骤如下：

1. 用较小的数去除较大的数，得到余数和一个新的除数
2. 用刚才的除数去除余数，再得到余数和一个新的除数
3. 重复以上步骤，直到余数为0，此时余数的前一个数就是最大公约数

下面是使用Python实现辗转相除法的代码：

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

接下来是最小公倍数的求解。它的公式如下：最小公倍数=两数之积/最大公约数。结合刚才求出的最大公约数，我们可以利用Python来实现最小公倍数的计算：

def lcm(a, b):
    return a * b // gcd(a, b)

最后，我们可以编写一个程序来输出给定两个正整数的最大公约数和最小公倍数。代码如下：

a = int(input("请输入第一个正整数："))
b = int(input("请输入第二个正整数："))

print("最大公约数为：", gcd(a, b))
print("最小公倍数为：", lcm(a, b))

使用上述代码，我们就可以求出两个正整数的最大公约数和最小公倍数了。

### 回答3：
最大公约数，即两个正整数中共有的约数中最大的一个。最小公倍数，即两个正整数中共有的倍数中最小的一个。

求最大公约数：

1. 辗转相除法：

辗转相除法又称为欧几里得算法，使用较为广泛。具体步骤如下：

（1）用两个正整数中较小的数去除较大的数，再用余数去除小的数，如此循环，直到余数为0为止，此时小的数即为最大公约数。

（2）若两个数中有一个为0，另一个不为0，则最大公约数为不为0的那个数。

Python代码实现：

def gcd(a, b):
    if a < b:
        a, b = b, a # 若a小于b，则交换a,b的值
    while b: # 当b非零时，执行下面的操作
        a, b = b, a % b # 每次将b赋值给a，将a%b的值赋给b
    return a

2. 更相减损法：

更相减损法也是一种求最大公约数的方法。具体步骤如下：

（1）用两个正整数中较大的数减去较小的数，然后对差取绝对值再执行相同的操作，直到两个数相等为止。

（2）若两个数中有一个为0，另一个不为0，则最大公约数为不为0的那个数。

Python代码实现：

def gcd(a, b):
    if a < b:
        a, b = b, a # 若a小于b，则交换a,b的值
    while b: # 当b非零时，执行下面的操作
        a, b = b, abs(a - b) # 每次将b赋值给a，将|a-b|的值赋给b
    return a

求最小公倍数：

最小公倍数可以通过公式 lcm(a, b) = a * b / gcd(a, b) 求出。

Python代码实现：

def lcm(a, b):
    return a * b // gcd(a, b) # 注意要取整除 //，而不是普通除 /

完整代码实现：

def gcd(a, b):
    if a < b:
        a, b = b, a # 若a小于b，则交换a,b的值
    while b: # 当b非零时，执行下面的操作
        a, b = b, a % b # 每次将b赋值给a，将a%b的值赋给b
    return a

def lcm(a, b):
    return a * b // gcd(a, b) # 注意要取整除 //，而不是普通除 /

a, b = 12, 18
print("最大公约数：", gcd(a, b))
print("最小公倍数：", lcm(a, b))

运行结果：

最大公约数： 6
最小公倍数： 36