黑马程序员技术交流社区

标题: 怎么求最大公约数和最小公倍数 [打印本页]

---

作者: hi虚无缥缈    时间: 2015-6-5 21:15
标题: 怎么求最大公约数和最小公倍数
输入两个正整数m和n，求其最大公约数和最小公倍数。

---

作者: 天下1083    时间: 2015-6-6 10:13
提供思路参考下：
1> 用辗转相除法求最大公约数  
算法描述:  
m对n求余为a, 若a不等于0  
则 m < n, n < a, 继续求余  
否则 n 为最大公约数  
<2> 最小公倍数 = 两个数的积 / 最大公约数

---

作者: jx836202365    时间: 2015-6-7 09:45
辗转相除法我都忘了

---

作者: fanxing    时间: 2015-6-7 19:20


//最大公约数这个比较简洁
int gcd（int m,int n) {       if(m%n==0) printf("%d\n",n);
     else gcd(n,m%n);
}
//最大公约数都知道了，直接用m*n/最大公约数就是最小公倍数了

---

作者: tabor    时间: 2015-6-10 13:57
顺着2楼方法描述，改下第一个方法：
比较两个数大小，再做个逆序循环，次数与小数同，只要有一个数能同时求余为0，就是最大公约数

---

作者: 仁清    时间: 2015-6-16 17:31
用欧几里德算法（辗转相除法）求两个数的最大公约数的步骤如下：
1.先用小的一个数除大的一个数，得第一个余数；
2.再用第一个余数除小的一个数，得第二个余数；
3.又用第二个余数除第一个余数，得第三个余数；
　　这样逐次用后一个数去除前一个余数，直到余数是0为止。那么，最后一个除数就是所求的最大公约数（如果最后的除数是1，那么原来的两个数是互质数）。

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2