C++代码：最大公约数和最小公倍数 |21xrx.com

C++代码：最大公约数和最小公倍数

2023-06-22 17:05:51 深夜i -- --

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

在数学中，最大公约数是指两个或多个整数公共有约数中最大的一个，而最小公倍数指不小于该数的倍数中，最小的一个数。在计算机编程中，计算最大公约数和最小公倍数是常见的任务，下面将介绍 C++ 中如何实现这两个计算任务。

计算最大公约数的方法分为两种，一种是辗转相除法，另一种是更相减损术。下面是使用辗转相除法计算最大公约数的 C++ 代码：

#include

using namespace std;

int Gcd(int a, int b)

{

if (b == 0) return a;

int r = a % b;

return Gcd(b, r);

}

int main()

{

int a, b;

cin >> a >> b;

int gcd = Gcd(a, b);

cout << gcd << endl;

return 0;

}

使用更相减损术计算最大公约数的思路是，对两个整数做减法，再将减数和差做减法，重复这个过程直到两个整数相等，此时的公共值即为最大公约数。下面是使用更相减损术计算最大公约数的 C++ 代码：

#include

using namespace std;

int Gcd(int a, int b)

{

if (a == b) return a;

if ((a & 1) == 0 && (b & 1) == 0) return Gcd(a >> 1, b >> 1) << 1;

if ((a & 1) == 0) return Gcd(a >> 1, b);

if ((b & 1) == 0) return Gcd(a, b >> 1);

return Gcd(abs(a - b), min(a, b));

}

int main()

{

int a, b;

cin >> a >> b;

int gcd = Gcd(a, b);

cout << gcd << endl;

return 0;

}

计算最小公倍数的方法分为两种，一种是根据最大公约数计算，另一种是直接计算。下面是根据最大公约数计算最小公倍数的 C++ 代码：

#include

using namespace std;

int Gcd(int a, int b)

{

if (b == 0) return a;

int r = a % b;

return Gcd(b, r);

}

int Lcm(int a, int b)

{

int gcd = Gcd(a, b);

return a / gcd * b;

}

int main()

{

int a, b;

cin >> a >> b;

int lcm = Lcm(a, b);

cout << lcm << endl;

return 0;

}

直接计算最小公倍数的思路是，多次循环，找出两个数的公倍数，直到找到最小的公倍数。下面是直接计算最小公倍数的 C++ 代码：

#include

using namespace std;

int Lcm(int a, int b)

{

int large = max(a, b), small = min(a, b);

for (int i = 1; i <= small; i++) {

int mul = large * i;

if (mul % small == 0)

return mul;

}

return large * small;

}

int main()

{

int a, b;

cin >> a >> b;

int lcm = Lcm(a, b);

cout << lcm << endl;

return 0;

}

最大公约数和最小公倍数是数学中常见的计算问题，同样也是编程中常见的任务。使用 C++ 实现这两个任务的方法是多种多样的，以上代码仅供参考。

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

下一篇: C++中的头文件iostream.h

评论区

()

相似文章