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

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

在C语言中，我们可以使用多种方法来计算两个整数的最大公约数(GCD)和最小公倍数(LCM),以下是几种常见的实现方法：

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

#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);
    if (num1 <= 0 || num2 <= 0) {
        printf("请输入正整数！\n");
        return 1;
    }
    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;
}
// 计算最小公倍数（利用GCD）
int lcm(int a, int b) {
    return (a * b) / gcd(a, b);
}

更相减损术

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

递归实现（辗转相除法）

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

枚举法（适用于较小数字）

#include <stdio.h>
// 函数声明
int gcd_enumeration(int a, int b);
int lcm_enumeration(int a, int b);
int main() {
    int num1, num2;
    printf("请输入两个正整数: ");
    scanf("%d %d", &num1, &num2);
    if (num1 <= 0 || num2 <= 0) {
        printf("请输入正整数！\n");
        return 1;
    }
    printf("最大公约数(GCD)是: %d\n", gcd_enumeration(num1, num2));
    printf("最小公倍数(LCM)是: %d\n", lcm_enumeration(num1, num2));
    return 0;
}
// 枚举法计算最大公约数
int gcd_enumeration(int a, int b) {
    int gcd = 1;
    for (int i = 1; i <= a && i <= b; i++) {
        if (a % i == 0 && b % i == 0) {
            gcd = i;
        }
    }
    return gcd;
}
// 枚举法计算最小公倍数
int lcm_enumeration(int a, int b) {
    int lcm = a > b ? a : b;
    while (1) {
        if (lcm % a == 0 && lcm % b == 0) {
            return lcm;
        }
        lcm++;
    }
}

注意事项

1. 所有方法都假设输入是正整数，程序中包含了输入验证
2. 最小公倍数可以通过最大公约数计算：LCM(a,b) = (a*b)/GCD(a,b)
3. 辗转相除法（欧几里得算法）是最常用且效率最高的方法
4. 对于非常大的数字，需要注意整数溢出问题，可以使用long long类型

选择哪种方法取决于具体需求和性能考虑，对于大多数情况，方法一（辗转相除法）是最佳选择。