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

在C语言中,计算两个数的最大公约数（GCD, Greatest Common Divisor）和最小公倍数（LCM, Least Common Multiple）是常见的数学问题，以下是几种实现方法：

使用欧几里得算法（辗转相除法）求GCD

欧几里得算法是一种高效计算GCD的方法,基于以下原理：

gcd(a, b) = gcd(b, a % b)，直到 b == 0，a 就是GCD。

代码实现

#include <stdio.h>
// 计算最大公约数（GCD）
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}
int main() {
    int num1, num2;
    printf("请输入两个正整数: ");
    scanf("%d %d", &num1, &num2);
    int result_gcd = gcd(num1, num2);
    printf("最大公约数（GCD）: %d\n", result_gcd);
    return 0;
}

示例

输入：12 18
输出：最大公约数（GCD）: 6

计算最小公倍数（LCM）

最小公倍数可以通过GCD计算：

lcm(a, b) = (a * b) / gcd(a, b)

代码实现

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

示例

输入：12 18
输出：

最大公约数（GCD）: 6
最小公倍数（LCM）: 36

递归实现GCD

欧几里得算法也可以用递归方式实现：

代码

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

处理负数

如果输入可能是负数,可以取绝对值后再计算：

代码

#include <stdio.h>
#include <stdlib.h> // 用于 abs()
int gcd(int a, int b) {
    a = abs(a);
    b = abs(b);
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}
int main() {
    int num1, num2;
    printf("请输入两个整数（可正可负）: ");
    scanf("%d %d", &num1, &num2);
    int result_gcd = gcd(num1, num2);
    printf("最大公约数（GCD）: %d\n", result_gcd);
    return 0;
}

你可以根据需求选择合适的方法,如果只是计算GCD和LCM，欧几里得算法（迭代）是最推荐的方案。