C/C++最大公因数、最小公倍数,辗转相除法,原理-创新互联

1. 原理介绍

根据数学原理

为达日等地区用户提供了全套网页设计制作服务,及达日网站建设行业解决方案。主营业务为成都网站设计、成都网站制作、达日网站设计,以传统方式定制建设网站,并提供域名空间备案等一条龙服务,秉承以专业、用心的态度为用户提供真诚的服务。我们深信只要达到每一位用户的要求,就会得到认可,从而选择与我们长期合作。这样,我们也可以走得更远!

两个整数的大公因数=两个整数之间比较小的那个数字与两者相处所得余数的大公因数。

两个整数的最小公倍数=两个数的乘积除以他们的大公因数。

2.算法实现

那么根据原理,其实就是除数与余数的一个车轮战,这也是我们辗转相除法的原理,并且只要求出大公因数,最小公倍数也就解决了。

3. 代码实现
#includeint max_in(int a,int b)//默认a>b
{
    if(a%b==0) return b;
    else {a=a%b;max_in(b,a);}
}
int main()
{
	int a,b,t;
	scanf("%d %d",&a,&b);//注意输入格式
	if(b>a) {t=b;b=a;a=t;};//比较一下大小,确保a是大的
	printf("大公因数是%d:\n",max_in(a,b));
	printf("最小公倍数是%d:\n",(a*b)/max_in(a,b));
	return 0;
}

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


当前标题:C/C++最大公因数、最小公倍数,辗转相除法,原理-创新互联
文章链接:http://pwwzsj.com/article/coigcs.html