已知两个正整数m和n,求其最大公约数和最小公倍数。 输入格式: 两个用空格分隔的正整数m和n。 输出格式: 只有一行,为两个用空格分隔的正整数,依次代表m和n的最大公约数和最小公倍数。测试用例保证m、n及其最小公

已知两个正整数\( m \)和\( n \)，可以使用欧几里得算法（Euclidean algorithm）来求它们的最大公约数（Greatest Common Divisor, GCD），然后通过公式 \( \text{LCM}(m, n) = \frac{|m \times n|}{\text{GCD}(m, n)} \) 来计算它们的最小公倍数（Least Common Multiple, LCM）。下面是步骤：

1. 如果\( n = 0 \)，那么最大公约数是\( m \)，最小公倍数就是\( |m| \)（因为任何数乘以0的结果都是0）。
2. 否则，用\( m \)除以\( n \)得到余数\( r \)，将\( n \)更新为原来的\( m \)，\( m \)更新为\( n \)，即\( m = n \), \( n = r \)。
3. 重复这个过程，直到余数\( r = 0 \)，此时的\( n \)就是最大公约数。

求出最大公约数之后，最小公倍数可以通过上述公式直接计算。

输入样例：

14 21

输出样例：

7 42

相关问题

已知两个正整数m和n，求其最大公约数和最小公倍数。 输入格式: 两个用空格分隔的正整数m和n。 输出格式: 只有一行，为两个用空格分隔的正整数，依次代表m和n的最大公约数和最小公倍数。测试用例保证m、n及其最小公倍数可以用int存储。C语言

在C语言中，计算两个正整数的最大公约数（GCD, Greatest Common Divisor）和最小公倍数（LCM, Least Common Multiple）通常采用欧几里得算法（Euclidean Algorithm）和公式：gcd(a, b) = gcd(b, a mod b)，lcm(a, b) = |a * b| / gcd(a, b)。

以下是一个简单的C语言函数来实现这个功能：

#include <stdio.h>

// 定义最大公约数和最小公倍数的辅助函数
int gcd(int m, int n) {
    while (n != 0) {
        int temp = m % n;
        m = n;
        n = temp;
    }
    return m;
}

// 计算最小公倍数
int lcm(int m, int n) {
    return (m * n) / gcd(m, n);
}

int main() {
    int m, n;
    printf("请输入两个正整数m和n: ");
    scanf("%d %d", &m, &n);

    int gcd_value = gcd(m, n);
    int lcm_value = lcm(m, n);

    printf("最大公约数: %d\n", gcd_value);
    printf("最小公倍数: %d\n", lcm_value);

    return 0;
}

当你运行这个程序并输入两个正整数时，它会输出这两个数的最大公约数和最小公倍数。

编写程序，产生两个0~100之间(包含0和100)的随机整数a和b，求这两个整数的最大公约数和最小公倍数。运行效果如图3-21所示。 整数1 = 88，整数2 = 16 最大公约数 =8，最小公倍数=176 图3-21 最大公约数和最小公倍数运行效果 提示： (1)可以利用“random.randint(0,100)”的语句形式生成0~100之间(包含0和100)的随机整数。 (2)利用“辗转相除法”求最大公约数，具体算法如下： ①对于已知的两个正整数m、n，使得m>n。 ②m除以n得余数r。 ③若r0，则令mn，nr，继续相除得到新的余数r。若仍然r0，则重复此过程，直到r=0为止。最后的m就是最大公约数。 (3)求得了最大公约数后，最小公倍数就是已知的两个正整数之积除以最大公约数的商

以下是程序的代码：

import random

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

a = random.randint(0, 100)
b = random.randint(0, 100)

print("整数1 =", a, "，整数2 =", b)

gcd_ab = gcd(a, b)
lcm_ab = a * b // gcd_ab

print("最大公约数 =", gcd_ab, "，最小公倍数 =", lcm_ab)

运行效果如下：

整数1 = 88 ，整数2 = 16
最大公约数 = 8 ，最小公倍数 = 176

注意：这里使用了辗转相除法求最大公约数，最小公倍数则是通过已知的两个正整数之积除以最大公约数的商得到的。