c++实现求最大公因数和最小公倍数

闲聊 无标签
1 587
GS
GS 自成一派 2023-09-05 21:03:47
Lv:29级
C++
#include<iostream>
using namespace std;
int GCD(int a,int b);
int LCM(int a,int b);
int main()
{
int num1,num2,gcd,lcm;
cout<<"求两个数的最大公约数及最小公倍数"<<endl<<endl;
cout<<"请输入两个数:";
cin>>num1>>num2;
gcd=GCD(num1,num2);
lcm=LCM(num1,num2);//输出最大公约数和最小公倍数
cout<<"最大公约数为:"<<gcd<<endl;
cout<<"最小公倍数为:"<<lcm<<endl;
system("pause");
return 0;
}
int GCD(int num1,int num2)
{
if(num1%num2==0)
return num2;
else return  GCD(num2,num1%num2);
}
int LCM(int a,int b)
{
int temp_lcm;
temp_lcm=a*b/GCD(a,b);//最小公倍数等于两数之积除以最大公约数
return temp_lcm;
}

楼主签名:Admin.Gs 站长故事
回帖
回复列表
  • GS
    2023-09-05 21:22:41
    用辗转相除法求最大公因数 

     辗转相除法的流程图如下:

    Image

     其中,输入保证a>b。 参考代码如下:

    #include <iostream>
    using namespace std;
    
    int main(){<!-- -->
    int a, b;
    cin >> a >> b;
    // 假设确保 a > b
    while(a % b != 0){<!-- -->
    int c = a % b;
    a = b;
    b = c;
    }
    cout << b << endl;
    return 0;
    }
    特别的,如果能用头文件algorithm的话,可以直接使用__gcd(int a, int b)函数来算最小公因数。我用的dev-c++是可以跑的通的。
    参考代码如下:

    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    int main(){
    	int a, b;
    	cin >> a >> b;
    	int n = __gcd(a, b);
    	cout << n << endl;
    	return 0;
    } 
    
    最小公倍数可以通过求得的最大公因数来计算。
    最小公倍数=a*b/最大公因数

    0 回复

遵守各国法律法规 严谨违规内容

  • QQ群:1140251126
  • Email:admin@admin.gs
  • 本站可以自由发布正规网站外链
  • 本站域名 admin.gs 其它皆为闲置域名
本站热帖
01 本站主题是啥 110
02 刚发现一个免费1年的SSL证书 108
03 teacher.run百度收录6000+并持续更新,续费到30年 94
04 windows系统全系列激活工具,HEU KMS Activator 93
05 QQ名片满级会员展示生成源码 89
06 飞沙电视TV,去除购物台绿化版! 86
07 Windows10极致优化,全套做完提速200%,让你的电脑直接起飞 85
08 谁推荐一下免费CDN或收费CDN 83
09 一个好看错误面页代码 79
10 一个非常好看科幻html博客源码 78
推荐主机