C++如何求最大公约数 |21xrx.com

2023-07-05 12:29:04 深夜i 33 0

C++ 最大公约数算法循环递归

在使用C++编程时，经常需要求解最大公约数。最大公约数是两个数的最大公因数，是C++编程中常用的一个概念。这里介绍两种方法来求最大公约数。

方法一：辗转相除法

辗转相除法是求最大公约数的一种简单而有效的方法。核心思想是用较大的数去除以较小的数，然后将除数与余数交换位置，反复进行除法运算，直到余数为零，此时最大公约数即为除数。

下面是采用辗转相除法的C++代码实现：

int gcd(int a, int b)
{
  while(b != 0)
  
    int temp = a % b;
    a = b;
    b = temp;
  
  return a;
}

方法二：欧几里得算法

欧几里得算法也称为辗转相减法，它是另一种求最大公约数的方法。核心思想是不断将较大的数减去较小的数，直到两个数相等，此时的数就是最大公约数。

下面是采用欧几里得算法的C++代码实现：

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

以上是两种求最大公约数的方法，虽然它们的实现方式不同，但是都能够有效地求解最大公约数。在实际编程中，根据需要选择合适的方法即可。

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

下一篇: C++中的void函数或void类型的变量是什么？

相似文章