C语言如何求多个数的最小公倍数？

C语言求最小公倍数（LCM）

在C语言中,求两个或多个数的最小公倍数（Least Common Multiple, LCM）可以通过以下几种方法实现：

利用最大公约数（GCD）

最小公倍数与最大公约数之间有数学关系：LCM(a, b) = (a * b) / GCD(a, b)

#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("%d 和 %d 的最小公倍数是: %d\n", num1, num2, 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) {
    // 防止a*b溢出，可以改为 (a / gcd(a,b)) * b
    return (a / gcd(a, b)) * b;
}

直接遍历法

#include <stdio.h>
int lcm(int a, int b);
int main() {
    int num1, num2;
    printf("请输入两个正整数: ");
    scanf("%d %d", &num1, &num2);
    printf("%d 和 %d 的最小公倍数是: %d\n", num1, num2, lcm(num1, num2));
    return 0;
}
int lcm(int a, int b) {
    int greater = (a > b) ? a : b;
    while (1) {
        if (greater % a == 0 && greater % b == 0) {
            return greater;
        }
        greater++;
    }
}

递归法（利用GCD）

#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("%d 和 %d 的最小公倍数是: %d\n", num1, num2, lcm(num1, num2));
    return 0;
}
// 递归计算GCD
int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}
// 计算LCM
int lcm(int a, int b) {
    return (a / gcd(a, b)) * b;
}

扩展：求多个数的最小公倍数

#include <stdio.h>
int gcd(int a, int b);
int lcm(int a, int b);
int array_lcm(int arr[], int n);
int main() {
    int n;
    printf("请输入数字的个数: ");
    scanf("%d", &n);
    int arr[n];
    printf("请输入%d个正整数: ", n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    printf("这些数字的最小公倍数是: %d\n", array_lcm(arr, n));
    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) {
    return (a / gcd(a, b)) * b;
}
int array_lcm(int arr[], int n) {
    int result = arr[0];
    for (int i = 1; i < n; i++) {
        result = lcm(result, arr[i]);
    }
    return result;
}

方法都可以有效地计算最小公倍数,选择哪种方法取决于具体需求和性能考虑，方法一（利用GCD）通常是最高效的。