C语言中求最大公约数和最小公倍数的函数：gcd()和lcm() |21xrx.com

2023-06-15 19:23:55 深夜i -- --

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

C语言中求最大公约数和最小公倍数的函数：gcd()和lcm()

在C语言中，我们经常需要求两个数的最大公约数和最小公倍数。为了方便，我们可以自己编写一个函数来完成这个任务。在C语言中，有两个函数可以帮助我们实现求最大公约数和最小公倍数的功能，它们是gcd()和lcm()函数。

gcd()函数用于求两个数的最大公约数，其原理是使用欧几里得算法。这个算法基于这样一个事实：如果a和b是两个整数，且a>b，那么它们的最大公约数等于a除以b的余数r和b之间的最大公约数。我们可以使用递归的方式实现这个算法，代码如下：


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

在这个函数中，如果b等于0，则a就是它们的最大公约数；否则，我们需要不断递归，直到b等于0。在每一次递归中，a变成原来的b，b变成原来的a除以b的余数。

lcm()函数用于求两个数的最小公倍数，其原理是使用最大公约数。我们知道，如果a和b是两个整数，它们的最小公倍数等于a和b的积除以它们的最大公约数。因此，可以使用gcd()函数来实现lcm()函数，代码如下：


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

这个函数的实现非常简单，我们只需要使用gcd()函数求出a和b的最大公约数，然后将a和b的积除以最大公约数即可求出它们的最小公倍数。

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

下一篇: 探究Javascript的优缺点及内置对象

()

相似文章