C++求最大公约数和最小公倍数的方法 |21xrx.com

C++求最大公约数和最小公倍数的方法

2023-07-02 04:31:20 深夜i 16 0

C++ 最大公约数最小公倍数方法

C++是一种功能强大的编程语言，可以通过它来求解数学问题，如求最大公约数和最小公倍数。这两个数学概念在日常生活中也经常使用。

最大公约数是指两个或多个正整数共有的约数中最大的一个，最小公倍数则是指两个或多个正整数的公共倍数中，最小的一个。任何两个正整数都有一个最大公约数和一个最小公倍数。

C++中求最大公约数和最小公倍数的方法如下：

求最大公约数

1.使用欧几里德算法

欧几里德算法，也称辗转相减法，是一种求最大公约数的方法。它的基本思想是用两个数中较大的数减去较小的数，然后用余数作为新的小数，继续重复这个过程，直到余数为0，此时得到的最大公约数就是较小的数。

代码实现如下：

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

2.使用更相减损术

更相减损术是一种比较简单但效率较低的求最大公约数的方法。它的基本思想是用两个数中较大的数减去较小的数，然后不断重复这个过程，直到两个数相等为止。

代码实现如下：

int gcd(int a, int b)
{
  while (a != b)
  {
    if (a > b)
    
      a = a - b;
    
    else
    
      b = b - a;
    
  }
  return a;
}

求最小公倍数

1.使用最大公约数

根据数学定理，两个数的最大公倍数等于这两个数的积除以它们的最大公约数。因此，可以先求得这两个数的最大公约数，然后再计算最小公倍数。

代码实现如下：

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

2.使用循环

根据数学定理，两个数的最小公倍数是这两个数的倍数中，最小的一个。因此，可以通过循环遍历这两个数的倍数，找到最小公倍数。

代码实现如下：

int lcm(int a, int b)
{
  int i, max;
  max = (a > b) ? a : b;
  for (i = max; ; i += max)
  {
    if (i % a == 0 && i % b == 0)
    
      return i;
    
  }
}

以上是C++中求最大公约数和最小公倍数的方法，可以根据实际情况选择适合自己的方法进行求解。通过掌握这些方法，可以更好地应对数学问题的编程求解。

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

下一篇: 【教程】C++学习之如何阅读程序

评论区

相似文章