黑马程序员技术交流社区

标题: 求两个正整数的最大公约数和最小公倍数 [打印本页]

作者: 羊口羊口羊 时间: 2015-9-8 20:37
标题: 求两个正整数的最大公约数和最小公倍数
这个是参考别人的代码编出来的，我不是很明白为什么用碾除法就能得到两个数的最大公约数，有知道的同学分享一下的咩！！？？？

QQ图片20150908203335.png (116.53 KB, 下载次数: 5)

作者: lixj1991 时间: 2015-9-10 15:17
设a和b的最大公约数是x。设a>b。
∵a%x=0，b%x=0
∴（b*n）%x=0
∴（a-b*n）%x=0.//同余具有可加减性。......[1]
设n=[a÷b]//取整除法，
则a-b*n就成为了a÷b的余数。
∴（a%b）%x=0......[2] //和[1]为相同的式子
于是a和b的最大公约数，同时也是a÷b的余数的最大公约数。
于是求最大公约数的时候，可以选择这3个数中，较小的两个数进行，不影响最大公约数的整除性。
因此使用取余的方法不断缩小a和b的值的时候，最大公约数的整除性仍然传递并且保留下来了。
最后当a%b=0的时候，b就被a整除了。于是在不断取余数的过程中，最大公约数就出现了。//while循环的终止条件是b=0

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

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