21xrx.com
2025-07-03 07:18:26 Thursday
文章检索 我的文章 写文章
C++中的最小公倍数算法
2023-07-05 02:39:14 深夜i     30     0
C++ 最小公倍数 算法

最小公倍数是指两个或多个整数公共的倍数中最小的一个。在C++中,我们可以使用一种基于辗转相除的算法来求最小公倍数。

这种算法被称为辗转相除法或欧几里得算法,它的原理是:如果a整除b,那么b和a%b(即a除以b的余数)的最大公约数就是a和b的最大公约数;反之,如果b不能被a整除,那么a%b和b的最大公约数就是a和b的最大公约数。使用这种方法的好处是可以快速的求出两个数的最大公约数。

我们可以使用递归函数来实现这个算法:

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

有了最大公约数,我们就可以方便的求出最小公倍数。根据数学原理,两个整数的最小公倍数就是它们的乘积除以最大公约数。

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

这个函数可以计算两个整数的最小公倍数。当我们需要求多个整数的最小公倍数时,可以利用这个函数循环计算。

int lcm( int arr[], int n )
{
  int ans = arr[0];
  for( int i = 1; i < n; i++ )
  {
    ans = lcm( ans, arr[i] );
  }
  return ans;
}

这就是C++中求最小公倍数的算法。使用这个算法,我们可以很方便地求出两个或多个整数的最小公倍数。

  
  

评论区