C语言 如何求两整数的最大公约数与最小公倍数

下面是C语言如何求两整数的最大公约数与最小公倍数的完整攻略。

求最大公约数

理论知识

两个数的最大公约数是它们的公共因数中最大的一个数。求两个数的最大公约数也就是求这两个数的所有公因数中最大的一个数。

有很多算法可以用来求最大公约数，其中最常用的两种是辗转相减法和欧几里得算法（辗转相除法）。

代码示例

#include <stdio.h>
int GCD(int m, int n) {
    while(m != n) {
        if(m > n) {
            m = m - n;
        } else {
            n = n - m;
        }
    }
    return m;
}
int main() {
    int a, b;
    printf("请输入两个整数：\n");
    scanf("%d%d", &a, &b);
    printf("%d和%d的最大公约数为%d\n", a, b, GCD(a, b));
    return 0;
}

示例说明

假设 a = 12，b = 20。

我们就可以从 a - b 开始，得到 8 和 20。然后再从 20 - 8 得到 12 和 8。此时它们相等，因此得到了 4 和 8 的最大公约数，即 4。

求最小公倍数

理论知识

两个数的最小公倍数是它们的公共倍数中最小的一个数。求两个数的最小公倍数也就是求这两个数的所有公倍数中最小的一个数。

最小公倍数等于两个数的乘积除以它们的最大公约数。

代码示例

#include <stdio.h>
int GCD(int m, int n) {
    while(m != n) {
        if(m > n) {
            m = m - n;
        } else {
            n = n - m;
        }
    }
    return m;
}
int LCM(int m, int n) {
    return m * n / GCD(m, n);
}
int main() {
    int a, b;
    printf("请输入两个整数：\n");
    scanf("%d%d", &a, &b);
    printf("%d和%d的最小公倍数为%d\n", a, b, LCM(a, b));
    return 0;
}

示例说明

假设 a = 12，b = 20。

首先求得 a 和 b 的最大公约数 GCD(a, b) = 4。

然后通过最小公倍数公式 LCM(a, b) = a * b / GCD(a, b) 得到最小公倍数 LCM(a, b) = 60。

以上就是 C 语言如何求两整数的最大公约数与最小公倍数的详细攻略。