C++程序实现辗转相除法求最大公约数和最小公倍数 |21xrx.com

2023-06-30 15:31:34 深夜i -- --

C++ 辗转相除法最大公约数最小公倍数

辗转相除法是一种求最大公约数和最小公倍数的有效方法，特别适用于大数的计算。使用C++语言来实现这个算法需要用到循环、条件判断等基本语句。

最大公约数的求解方法：

设a、b为两个整数（a>b），a%b=c，欧几里得算法基本原理：gcd(a,b)=gcd(b,c)，以此类推直到c=0，则gcd(a,b)=b。

最小公倍数的求解方法：

lcm(a,b)=a*b/gcd(a,b)

接下来，我们就来实现这个算法。

代码如下：

#include

using namespace std;

int main()

{

int a,b,c,gcd,lcm;

//接收用户输入的数据

cout<<"请输入两个整数a和b："<

cin>>a>>b;

//循环计算余数直到余数为0

while(b!=0)

c=a%b;

a=b;

b=c;

//输出最大公约数

gcd=a;

cout<<"最大公约数为："< <

//计算最小公倍数

lcm=gcd*(a/gcd)*(b/gcd);

//输出最小公倍数

cout<<"最小公倍数为："< <

return 0;

}

先定义了变量a、b、c、gcd、lcm。通过用户的输入，将a、b两个整数存入变量中。进入while循环，直到变量b取余数为0时跳出循环。在while循环中，将a%b的结果存入变量c，同时用b更新a的值，b更新为c的值。最终得到最大公约数gcd=a。

根据最大公约数的公式，可以计算出最小公倍数lcm。最后输出最大公约数gcd和最小公倍数lcm。

以上C++代码实现了辗转相除法求解最大公约数和最小公倍数，可以有效地解决相应的问题，可供各位程序员参考和使用。

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

下一篇: C++利用输入输出流实现文章复制

()

相似文章