C++语言求解最大公约数和最小公倍数 |21xrx.com

C++语言求解最大公约数和最小公倍数

2023-07-07 22:41:38 深夜i -- --

C++ 最大公约数最小公倍数

在编程中，最大公约数和最小公倍数是经常使用的两个名词。对于C++语言来说，实现求解最大公约数和最小公倍数也是比较简单的。本文将简单介绍如何使用C++语言求解最大公约数和最小公倍数。

1. 求解最大公约数

最大公约数，也叫最大公因数，是指几个数公共的约数中最大的一个数。在C++中，使用辗转相减法可以求出几个数的最大公约数。代码如下：


#include <iostream>
using namespace std;
int gcd(int a, int b)
{
  if (a == b)
    return a;
  else if (a > b)
    return gcd(a-b, b);
  else
    return gcd(a, b-a);
}
int main()
{
  int a, b;
  cout << "请输入两个数：" << endl;
  cin >> a >> b;
  cout << "它们的最大公约数是：" << gcd(a, b) << endl;
  return 0;
}

在上面的代码中，函数`gcd()`采用递归的方式实现最大公约数的求解。辗转相减法的基本思想是：将两个数中较大的数减去较小的数，得到一个新的数。然后，继续利用这两个数进行相减，直到有一个数为零，此时所剩下的另一个数就是原来两个数的最大公因数。

2. 求解最小公倍数

最小公倍数，是指几个数公共的倍数中最小的一个数。在C++中，通过计算两个数的乘积除以最大公约数可以求出它们的最小公倍数。代码如下：


#include <iostream>
using namespace std;
int gcd(int a, int b)
{
  if (a == 0)
    return b;
  else
    return gcd(b % a, a);
}
int lcm(int a, int b)
{
  return a * b / gcd(a, b);
}
int main()
{
  int a, b;
  cout << "请输入两个数：" << endl;
  cin >> a >> b;
  cout << "它们的最小公倍数是：" << lcm(a, b) << endl;
  return 0;
}

在上面的代码中，函数`lcm()`通过调用`gcd()`函数来求出最小公倍数。最小公倍数等于两个数的乘积除以它们的最大公约数。因此，函数`lcm()`的实现就是将两个数相乘再除以它们的最大公约数。

总之，对于C++程序员来说，求解最大公约数和最小公倍数是一项很基本的任务。只要掌握了相关的算法，就可以轻松地完成这项任务并得到正确的答案。

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

下一篇: 如果删除了C++，会对我们的计算机产生什么影响？

评论区

()

相似文章