首页3-2 最大公约数和最小公倍数 c语言

3-2 最大公约数和最小公倍数 c语言

时间: 2025-02-18 14:08:59 浏览: 47

### C语言实现最大公约数和最小公倍数在C语言中，可以通过欧几里得算法来高效地计算两个整数的最大公约数（GCD），进而利用该结果进一步求解最小公倍数（LCM）。具体来说，对于任意两个正整数`a`和`b`，其最小公倍数可通过下述公式得出： \[ \text{LCM}(a,b)=\frac{|a*b|}{\text{GCD}(a,b)} \] #### 计算最大公约数 (GCD) 为了提高效率，采用迭代版本的欧几里得算法。此方法基于这样一个事实：两个数的最大公约数等于其中较小的那个数与两数相除余数之间的最大公约数。 ```c #include <stdio.h> // 定义gcd函数用于返回两个参数的最大公约数值 int gcd(int a, int b){ while(b != 0){ int temp = b; b = a % b; a = temp; } return a; // 返回最终的结果即为所求的最大公约数 } ``` 上述代码实现了求取两个给定整数之间最大公约数的功能[^1]。 #### 计算最小公倍数 (LCM) 有了前面定义好的`gcd()`函数之后，可以很容易地写出另一个辅助函数来获取最小公倍数: ```c // 基于已有的gcd()函数构建lcm() long long lcm(long long a, long long b){ return abs((a / gcd(a, b)) * b); // 防止溢出先做除法再乘积 } ``` 这段代码展示了如何根据之前提到的关系式去计算两个整数间的最小公倍数[^2]。最后给出完整的测试案例以便验证这两个功能是否正常工作： ```c int main(){ printf("请输入两个整数:\n"); long long num1,num2; scanf("%lld%lld",&num1,&num2); printf("最大公约数：%d\n", gcd(num1, num2)); printf("最小公倍数：%lld\n", lcm(num1, num2)); return 0; } ``` 这段程序允许用户输入一对整数，并输出它们对应的最大公约数以及最小公倍数[^3]。

阅读全文