如何在C语言中求最大公约数 |21xrx.com

2023-06-18 05:18:16 深夜i -- --

C语言最大公约数辗转相除法更相减损术

在编程过程中，经常会涉及到求最大公约数的问题。C语言提供了多种方法来求解这个问题，本文将重点介绍其中的两种方法。

方法一：辗转相除法

辗转相除法也称为欧几里得算法，是求解最大公约数的一种常用的方法。其思想是：用较大数除以较小数，如果余数不为零，则两数的最大公约数等于较小数和余数的最大公约数，如此重复，直到余数为零，则较小数即为最大公约数。

代码示例：


int gcd(int x, int y) {
  if (x % y == 0)
    return y;
   else {
    return gcd(y, x % y);
  }
}

方法二：更相减损术

更相减损术也是一种求最大公约数的方法，其思想是：用较大数减去较小数，如果差为零，则两数的最大公约数等于较小数；如果差不为零，则将两数的差和较小数求最大公约数，如此重复，直到两数相等，则它们的值即为所求最大公约数。

代码示例：


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

通过以上两种方法，我们可以很容易地在C语言中求解最大公约数问题。

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

下一篇: Java编程常用缩写你都知道吗

()

相似文章