21xrx.com
2025-03-29 07:05:40 Saturday
文章检索 我的文章 写文章
使用Euclid算法求最大公因数的c语言实现
2023-06-18 19:34:02 深夜i     11     0
最大公因数 Euclid算法 c语言 递归 除余算法

在数学中，最大公因数是指能够同时整除给定的两个或多个整数的最大正整数。求最大公因数是数学中一个基本问题，也是计算机科学中常见的数学问题之一。Euclid算法是一种高效的求最大公因数的算法，其基本思想是不断用较小的数去除较大的数，直到两数相等为止，再返回它们的公因数。

下面是用c语言实现Euclid算法求最大公因数的代码：

#include
int gcd(int a, int b) {
  if (b == 0)
    return a;
  
  else {
    return gcd(b, a % b);
  }
}
int main() {
  int a = 28, b = 42;
  int result = gcd(a, b);
  printf("The gcd of %d and %d is %d", a, b, result);
  return 0;
}

在代码中，gcd函数使用递归的方法实现Euclid算法，当b等于0时，a即为最大公因数；否则，用b去除a的余数，继续递归求解。

使用上述代码可以求解出28和42的最大公因数，结果为14。

  
  

评论区