c语言求最大公约数与最小公背数

### C语言实现求解最大公约数和最小公倍数

#### 使用欧几里得算法求最大公约数 (GCD)

一种高效的方法来计算两个整数的最大公约数是使用欧几里得算法。该算法基于这样一个事实：两个正整数 \(a\) 和 \(b\) 的最大公约数等于较小的那个数与两数之差之间的最大公约数。

#include <stdio.h>

int gcd(int a, int b) {
    while(b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

这段代码实现了上述逻辑，通过不断取模直到余数为零为止[^1]。

#### 计算最小公倍数 (LCM)

一旦获得了 GCD 后，可以很容易地得到 LCM。因为对于任意一对正整数 \(a\) 和 \(b\), 它们的乘积等于它们各自质因子分解后的所有不同质因数幂次相加的结果；而这个结果又恰好等于这两个数各自的 GCD 与其对应的商的乘积：

\[ \text{LCM}(a,b)=|ab|/\text{GCD}(a,b)\]

因此，在已知 `gcd` 函数的情况下，可以通过下面的方式快速获得 lcm:

long long lcm(long long a, long long b){
    return abs((a / gcd(a, b)) * b);
}

这里需要注意的是为了防止溢出，先做除法再乘以另一个操作数[^3]。

#### 综合示例程序

将以上两种功能结合起来编写完整的 C 程序如下所示：

#include <stdio.h>
#include <stdlib.h> // For using the function 'abs'

// Function to compute GCD of two numbers.
int gcd(int a, int b);

// Function to calculate LCM based on previously defined GCD method.
long long lcm(long long a, long long b);

int main(){
    int num1, num2;

    printf("Enter two integers: ");
    scanf("%d %d", &num1, &num2);

    printf("The Greatest Common Divisor is : %d\n", gcd(num1,num2));
    printf("The Least Common Multiple is : %lld\n",lcm(abs(num1), abs(num2)));

    return 0;
}

/* Implementation of Euclidean algorithm */
int gcd(int a, int b){
    if (b == 0)
       return a;
    else
       return gcd(b, a % b);
}

/* Calculate LCM after getting GCD value from above function */
long long lcm(long long a, long long b){
    return ((a / gcd(a, b)) * b);
}

此段代码首先让用户输入两个整数，接着调用了之前定义好的函数去获取并打印出相应的 GCD 及 LCM 值[^2]。