C++代码求解最大公约数 |21xrx.com

C++代码求解最大公约数

2023-07-09 11:44:47 深夜i 22 0

C++ 代码最大公约数

最大公约数是指多个整数共有的约数中最大的一个。对于两个整数a和b来说，它们的最大公约数可以通过以下方式求得：

1. 如果a和b都为0，则它们没有最大公约数；

2. 如果其中一个数为0，另一个数为非零整数，则它们的最大公约数为非零整数；

3. 如果a和b都为非零整数，则可以使用辗转相除法（欧几里得算法）求解。具体步骤如下：

a) 用较大数除以较小数，得到商和余数；

b) 如果余数为0，则较小数即为最大公约数；

c) 如果余数不为0，则将较小数作为除数，余数作为被除数再进行相除，直到余数为0为止，此时除数即为最大公约数。

下面是使用C++语言实现求最大公约数的代码：

#include <iostream>
using namespace std;
int gcd(int a, int b) {  // 定义函数gcd，输入两个整数a、b，返回它们的最大公约数
  if (a == 0 && b == 0) 则它们没有最大公约数
    return 0;
  
  
  if (a == 0 || b == 0) {  // 如果其中一个数为0，另一个数为非零整数，则它们的最大公约数为非零整数
    return a + b;
  }
  
  int c = a % b;
  while (c != 0)   // 用辗转相除法求解最大公约数
    a = b;
    b = c;
    c = a % b;
  
  
  return b;
}
int main() {
  int a = 18;
  int b = 24;
  cout << "最大公约数为：" << gcd(a, b) << endl;  // 输出结果，最大公约数为6
  return 0;
}

使用上述代码，可以方便地求解多个整数的最大公约数。

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

下一篇: C++ 字符串的基本处理方法

评论区

相似文章