最大公约数最小公倍数c语言

C语言实现最大公约数(GCD)和最小公倍数(LCM)

在C语言中，计算最大公约数(GCD)和最小公倍数(LCM)有几种常见方法,下面我将介绍几种实现方式。

使用欧几里得算法计算GCD

欧几里得算法是计算最大公约数的高效方法：

#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) {
    // 使用公式 LCM(a,b) = (a*b)/GCD(a,b)
    return (a * b) / gcd(a, 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;
}

递归实现GCD

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

#include <stdio.h>
// 递归实现GCD
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);
    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;
}

处理负数的情况

如果需要处理负数,可以添加绝对值函数：

#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 lcm(int a, int b) {
    return abs(a * b) / gcd(a, 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;
}

计算多个数的GCD和LCM

如果要计算多个数的GCD和LCM,可以逐步计算：

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

代码提供了几种不同的实现方式，可以根据具体需求选择使用,欧几里得算法是最常用且高效的GCD计算方法。