1、辗转相除法
辗转相除法：以大数除以小数，如果能整除，那么小数就是所求的最大公约数。否则就用除数来除以余数。依此类推，直到一个除法能够整除，这时作为除数的数就是所求的最大公约数。
如两个整数a>b；a/b=商 余数c， a和b的最大公约数 就是 b和c的最大公约数
例如：求 4453 和 5767 的最大公约数时，可作如下除法．
5767÷4453＝1 余 1314
4453÷1314＝3 余 511
1314÷511 ＝2 余 292
511 ÷292 ＝1 余 219
292 ÷219 ＝1 余 73
219÷73＝3 于是得知，5767 和 4453 的最大公约数是 73。辗转相除法适用比较广，比短除法要好得多，它能保证求出任意两个数的最大公约数。
当两数很大时取模运算的性能差，引出下一个方法。
2、更相减损术：
文章知识点与官方知识档案匹配，可进一步学习相关知识Java技能树首页概览93540 人正在系统学习中
声明：本站部分文章及图片源自用户投稿，如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢！