关于求最大公约数算法的问题书上是说：1.输入m、n（m为被除数,n为除数）2.m/n得余数r.3.判断r=0?是的话n为最大公约数.4.否则讲n赋给m,r赋给n,循环2.我想问为什么能这么做?（为什么能用除数除

Question

关于求最大公约数算法的问题
书上是说：1.输入m、n（m为被除数,n为除数）2.m/n得余数r.3.判断r=0?是的话n为最大公约数.4.否则讲n赋给m,r赋给n,循环2.我想问为什么能这么做?（为什么能用除数除以余数一直循环?）

Answer 1

辗转相除法：如：求（45,72）
72/45 = 1 余 27 不等于0,再除
45 /27= 1 余 18 不等于0,再除
27/18= 1 余 9 不等于0,再除
18/9 = 2 余 0 等于0,结束.
所以 （45,72）=9