js实现辗转相除法求最大公约数

昨晚刷抖音，跳出的第一条是李永乐老师（清华大学2009届毕业生，现就职于北京人大附中）讲诉他为什么要当中学老师的视频，看完后被他圈粉了，就进入主页一直刷他的其余作品，其中一条就是《轻松Get辗转相除法求最大公约数》，哇！有意思，打开电脑，试试用js能不能写出这个算法。

先来复习一下什么是辗转相除法：

假设求104和40的最大公约数，我们知道，除法有被除数、除数、商、余数。所以，该题被除数为104，除数为40，进行一次除法运算后，商为2，余数为24。辗转相除法规定，当余数不为0时（即不能整除），就应该把上一次的除数作为下一次的被除数、上一次的余数作为下一次的除数再次进行除法运算，接着看余数能否为0。不为0，继续此方法做除运算；为0，此时的除数就是二者的最大公约数。理论很骨感，例子才丰满：

image

友情提醒，假如你想自己动手看看能不能用js写出这个算法，请不要继续往下翻，拿出纸笔开始构思吧！假如你是通过电脑浏览这篇文章的，你可以在这个页面上点击鼠标右键，选择检查（或者审查元素）以调出调试工具，在console标签下开始写你的js代码

1、使用递归

/* *@method gcd *@param { Number } a *@param { Number } b *@return { Number } a和b的最大公约数*/function gcd(a, b) {  if (a < b) {    // 利用es6数组解构方法巧妙地置换a和b的值，目的使a大于b    [a, b] = [b, a]  }  if (b === 0) {    return a  }  if (a % b !== 0) {    return gcd(b, a % b)  } else {    return b  }}// 调用gcd(104, 40) // 8gcd(40, 104) // 8gcd(40, 0) // 40

2、使用循环

/* *@method gcd *@param { Number } a *@param { Number } b *@return { Number } a和b的最大公约数*/function gcd(a, b) {  if (a < b) {    [a, b] = [b, a]  }  while (b !== 0) {    let remainder = a % b    a = b    b = remainder  }  return a}// 调用gcd(104, 40) // 8gcd(40, 104) // 8gcd(40, 0) // 40

网上还有一种叫做更相减损的方法，即始终拿大的减小的，所得差给本来大的一方，如此循环往复，直到两者相等，那么相等的这个数字就是最大公约数了，详见：

function gcd (a, b) {  if (a === b) {    return b  }  if (a > b) {    a -= b  } else {    b -= a  }  return gcd(a, b)}// 调用gcd(104, 40) // 8

总结：以上两种方法中，辗转相除法的效率较高。