21xrx.com
2024-09-19 09:37:45 Thursday
登录
文章检索 我的文章 写文章
C++中如何求最大公约数和最小公倍数
2023-06-24 08:26:41 深夜i     --     --
C++ 最大公约数 最小公倍数

在C++中，求最大公约数和最小公倍数的方法有很多种，这里我们介绍两种常用的方法。

方法一：辗转相除法

辗转相除法，也称为欧几里得算法，是求最大公约数的一种常用方法。其基本思想是用两个数中较小的数去除较大的数，再用余数去除较小的数，不断重复这个过程，直到余数为零为止，此时较小的数即为最大公约数。

示例代码：

int gcd(int a, int b) { 

  return b ? gcd(b, a % b) : a; 

}

int lcm(int a, int b) { 

  return a * b / gcd(a, b); 

}

方法二：枚举法

枚举法是求最大公约数和最小公倍数的一种简单粗暴的方法。其基本思想是先从两个数中较小的数开始枚举，找到能够同时被两个数整除的数，这样找到的最大的数即为最大公约数，最小公倍数则可以通过公式a*b/gcd(a,b)求得。

示例代码：

int gcd(int a, int b) { 

  int m = a, n = b; 

  while (m != n) { 

    if (m > n)// 交换m和n，使m比n小 

      swap(m, n); 

    n -= m; 

  } 

  return m; 

}

int lcm(int a, int b) { 

  return a * b / gcd(a, b); 

}

需要注意的是，在使用枚举法求解最大公约数时，一定要从较小的数开始枚举，否则可能会导致程序运行时间过长。

综上所述，求最大公约数和最小公倍数是C++中常见的问题，我们可以使用辗转相除法或枚举法来解决。在实际应用中，辗转相除法通常效率更高，但在对时间要求不高的场景下，使用枚举法求解问题也是可行的。

  
  

评论区

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