辗转相除法计算最大公约数和最小公倍数

辗转相除法也叫欧几里得算法，它可以用来计算两个整数的最大公约数。

最大公约数

对于两个正整数a和b，设r是它们的除法余数，即$r=a\%b$，则有

$\gcd(a,b) = \gcd(b,r)$

这个公式的解释是：a和b的最大公约数等于b和r的最大公约数。因为除法有余数，所以可以将a和b不断递归地替换为b和r，直到r为0为止。此时，b就是原来a和b的最大公约数。

例如，假设要求242和594的最大公约数：

1. 用242去除以594，得到余数：242 = 594 × 0 + 242
2. 用594去除以242，得到余数：594 = 242 × 2 + 110
3. 用242去除以110，得到余数：242 = 110 × 2 + 22
4. 用110去除以22，得到余数：110 = 22 × 5 + 0

由于余数为0，所以22和110的最大公约数即为242和594的最大公约数，即gcd(242, 594) = 22。

最小公倍数

两个数的最小公倍数是它们的公共倍数中最小的一个。最小公倍数可以用以下公式计算：

$\text{lcm}(a,b) = \dfrac{a \times b}{\gcd(a,b)}$

例如，假设要求242和594的最小公倍数，则可以先计算它们的最大公约数为22，然后用上面的公式计算：

$\text{lcm}(242,594) = \dfrac{242 \times 594}{22} = 6498$

相关问题

C语言辗转相除法计算最大公约数和最小公倍数

以下是使用C语言辗转相除法计算最大公约数和最小公倍数的示例代码：

#include <stdio.h>

int main() {
    int a, b, temp, gcd, lcm;

    printf("Enter two positive integers: ");
    scanf("%d %d", &a, &b);

    // 辗转相除法求最大公约数
    int x = a, y = b;
    while (y != 0) {
        temp = x % y;
        x = y;
        y = temp;
    }
    gcd = x;

    // 计算最小公倍数
    lcm = (a * b) / gcd;

    printf("GCD of %d and %d is %d\n", a, b, gcd);
    printf("LCM of %d and %d is %d\n", a, b, lcm);

    return 0;
}

运行结果：

Enter two positive integers: 12 18
GCD of 12 and 18 is 6
LCM of 12 and 18 is 36

输入两个整数，用辗转相除法计算最大公约数和最小公倍数

好的，输入两个整数：a 和 b。

首先，我们可以使用辗转相除法计算最大公约数：

1. 令 r1 = a，r2 = b，q = r1 // r2，r = r1 % r2。
2. 如果 r == 0，则最大公约数为 r2。
3. 如果 r != 0，则继续令 r1 = r2，r2 = r，q = r1 // r2，r = r1 % r2，重复步骤 2。

代码实现如下：

def gcd(a, b):
    r1, r2 = a, b
    while r2 != 0:
        q = r1 // r2
        r = r1 % r2
        r1, r2 = r2, r
    return r1

接下来，我们可以使用最大公约数计算最小公倍数：

最小公倍数 = a * b / 最大公约数

代码实现如下：

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

完整代码如下：

def gcd(a, b):
    r1, r2 = a, b
    while r2 != 0:
        q = r1 // r2
        r = r1 % r2
        r1, r2 = r2, r
    return r1

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

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

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

希望能对你有所帮助！