C语言如何高效求两数最大公约数与最小公倍数？

C语言求两个数的最大公约数和最小公倍数

在C语言中,我们可以使用多种方法来求两个数的最大公约数(GCD)和最小公倍数(LCM)，下面我将介绍几种常见的方法。

辗转相除法（欧几里得算法）

这是最常用的求最大公约数的方法,基于以下原理： gcd(a, b) = gcd(b, a % b) 直到 b 为 0

#include <stdio.h>
// 函数声明
int gcd(int a, int b);
int lcm(int a, int b);
int main() {
    int num1, num2;
    printf("请输入两个正整数: ");
    scanf("%d %d", &num1, &num2);
    // 计算并输出最大公约数
    printf("最大公约数(GCD)是: %d\n", gcd(num1, num2));
    // 计算并输出最小公倍数
    printf("最小公倍数(LCM)是: %d\n", lcm(num1, num2));
    return 0;
}
// 计算最大公约数的函数
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}
// 计算最小公倍数的函数
int lcm(int a, int b) {
    // 利用公式 LCM(a,b) = (a*b)/GCD(a,b)
    return (a * b) / gcd(a, b);
}

更高效的辗转相除法（递归实现）

递归实现可以使代码更简洁：

#include <stdio.h>
// 递归计算最大公约数
int gcd_recursive(int a, int b) {
    if (b == 0)
        return a;
    return gcd_recursive(b, a % b);
}
// 计算最小公倍数
int lcm(int a, int b) {
    return (a * b) / gcd_recursive(a, b);
}
int main() {
    int num1, num2;
    printf("请输入两个正整数: ");
    scanf("%d %d", &num1, &num2);
    printf("最大公约数(GCD)是: %d\n", gcd_recursive(num1, num2));
    printf("最小公倍数(LCM)是: %d\n", lcm(num1, num2));
    return 0;
}

更相减损术

这是中国古代数学家使用的算法,基于以下原理： gcd(a, b) = gcd(a-b, b) 当 a > b gcd(a, b) = gcd(a, b-a) 当 b > a 直到 a == b

#include <stdio.h>
// 使用更相减损术计算最大公约数
int gcd_subtraction(int a, int b) {
    while (a != b) {
        if (a > b)
            a = a - b;
        else
            b = b - a;
    }
    return a;
}
int lcm(int a, int b) {
    return (a * b) / gcd_subtraction(a, b);
}
int main() {
    int num1, num2;
    printf("请输入两个正整数: ");
    scanf("%d %d", &num1, &num2);
    printf("最大公约数(GCD)是: %d\n", gcd_subtraction(num1, num2));
    printf("最小公倍数(LCM)是: %d\n", lcm(num1, num2));
    return 0;
}

注意事项

1. 所有方法都假设输入的是正整数
2. 对于最小公倍数的计算,我们使用了公式 LCM(a,b) = (a*b)/GCD(a,b)
3. 辗转相除法（方法一和方法二）是最常用且效率最高的方法
4. 在实际应用中,应该考虑输入验证，确保用户输入的是正整数

三种方法都可以有效地计算两个数的最大公约数和最小公倍数,其中第一种方法（迭代实现的辗转相除法）是最推荐的实现方式。