软件编程
位置：首页>> 软件编程>> C语言>> C++ 实现求最大公约数和最小公倍数

C++ 实现求最大公约数和最小公倍数

作者：lqh　　发布时间：2023-10-30 10:49:23　

标签：最大公约数,最小公倍数

C++ 实现求最大公约数和最小公倍数

最大公约数

辗转相除法:


int maxDivisor(int a, int b)
{
 int c = b;
 while (a％b != 0)
 {
   c = a％b;
   a = b;
   b = c;
 }
 return c;
}

辗转相减法：


int maxDivisor(int a, int b)
{
 while (a != b)
 {
   if (a>b) a = a - b;
   else b = b - a;
 }
 return a;
}

输入两个正整数m和n，求其最大公约数和最小公倍数


#include<iostream>
using namespace std;

int main()
{
int m,n,t;
cout<<"请输入两个正整数："<<endl;
cin>>m>>n;
int x=m;//将最初的m和n的值分别用x和y保存起来，后面计算最小公倍数时需要用到
int y=n;
if(m<n){
t=m;//t为中间变量，来实现m与n的值的相互交换，保证被除数大于除数
m=n;
n=t;
}
int r=m％n;
while(r){//用n来除以m，直到m被n整除，循环终止，此时r的值为0，在c++中只有0才为假，任何非0的值都判断为真
m=n;//辗转相除法的核心就是用较大的数m去除较小的数n，如果刚好能整除，则m与n的最大公约数为n，如果不能整除，则将n的值赋给m，余数r赋给n，再进行下一次的相除，以此循环，直到整除为止
n=r;
r=m％n;

}
cout<<"最大公约数为："<<n<<endl;
cout<<"最小公倍数为："<<x*y/n<<endl;//两个数的最小公倍数等于两个数的乘积除最小除他们的最大公约数
return 0;
}

或


#include<iostream>
using namespace std;
int gys(int x,int y)
{
   return y? gys(y,x％y):x;
}
int main()
{  
   int x,y;
   cin>>x>>y;
   cout<<"最大公约数是：";
   cout<<gys(x,y)<<endl;
   cout<<"最小公倍数是:";
   cout<<(x*y)/gys(x,y);
   return 0;
}

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

来源：http://blog.csdn.net/xiong452980729/article/details/70237435

0
投稿

猜你喜欢

手机版 软件编程 asp之家 www.aspxhome.com