C语言中求最大公因数的方法及实现 |21xrx.com

C语言中求最大公因数的方法及实现

2023-06-15 09:16:56 深夜i 13 0

C语言最大公因数辗转相减法辗转相除法

在C语言中，求两个数的最大公因数是一项基本的算法问题。最常用的方法是辗转相减法和辗转相除法。辗转相减法指的是用较大的数减去较小的数，然后用得到的差值再去减较小的数，直到两数相等为止，这时的相等的数就是最大公因数。而辗转相除法的思路是将两个数都连续相除，直到余数为0，这时除数就是最大公因数。

下面是使用辗转相减法和辗转相除法的C语言实现代码：

（1）辗转相减法

#include 
int gcd(int a, int b) {
  if (a == b) return a;
  if (a < b) return gcd(b - a, a);
  return gcd(a - b, b);
}
int main() {
  int a, b;
  printf("请输入两个正整数：");
  scanf("%d %d", &a, &b);
  printf("它们的最大公约数是：%d\n", gcd(a, b));
  return 0;
}

（2）辗转相除法

#include 
int gcd(int a, int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
int main() {
  int a, b;
  printf("请输入两个正整数：");
  scanf("%d %d", &a, &b);
  printf("它们的最大公约数是：%d\n", gcd(a, b));
  return 0;
}

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

下一篇: 作为一名Java开发工程师

评论区

相似文章