如何用C语言程序求最大公约数和最小公倍数 |21xrx.com

2023-06-15 17:06:39 深夜i -- --

最大公约数最小公倍数辗转相除法

在数学中，最大公约数是两个或多个整数的公共因数中最大的一个，最小公倍数则是能够被这几个数整除的最小正整数。在实际应用中，求最大公约数和最小公倍数非常常见，比如在分数约分、分数加减乘除、时间换算等问题中，都需要用到这两个概念。

而在计算机编程中，C语言是一门十分常用的编程语言，在使用C语言编写程序时，我们也需要经常求最大公约数和最小公倍数。下面介绍两种常见的求解方法。

1. 辗转相除法

这是最常见的一种求最大公约数的方法。该算法的思想是利用两个数之间的余数，用较小的数不断去除较大的数，直到余数为0，此时不为0的那个数就是最大公约数。

实现代码如下：


int gcd(int a, int b) {
  if(b == 0) return a;
  else return gcd(b, a % b);
}

其中，a和b为要求最大公约数的两个数，调用该函数即可输出它们的最大公约数。

2. 最小公倍数 = 两数之积 ÷ 最大公约数

这个方法可以在求得最大公约数后，直接利用公式计算出最小公倍数。

代码实现如下：


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

其中，gcd(a, b)表示使用辗转相除法求出的a和b的最大公约数。

有了上述两个函数，我们就可以在程序中轻松求解最大公约数和最小公倍数了。

上一篇: idea打包java可执行jar包

下一篇: 从字符串到字符数组：Java中string转换为char数组的方法

()

相似文章