21xrx.com
2024-11-22 11:08:53 Friday
登录
文章检索 我的文章 写文章
C++中的最小公倍数算法
2023-07-05 02:39:14 深夜i     --     --
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++中求最小公倍数的算法。使用这个算法,我们可以很方便地求出两个或多个整数的最小公倍数。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复