JavaScript求一组数的最小公倍数和最大公约数常用算法详解【面向对象，回归迭代和循环】

JavaScript求一组数的最小公倍数和最大公约数常用算法详解

本文通过具体实例，详细解析了JavaScript中计算一组数字最大公约数与最小公倍数的常用算法，供读者参考学习。

所介绍的方法基于一种针对多个数求最小公倍数的变换算法，具体原理见附录部分。

最小公倍数的计算可由最大公约数推导得出。求最大公约数的具体步骤如下：

（1）在a1, a2, ..., an中找出最小的非零项aj；若存在多个相同的最小非零项，可任选其一。 （2）将aj以外的所有其他非零项ak替换为ak mod aj；若除aj外无其他非零项，则执行步骤（4）。 （3）返回步骤（1）继续循环。 （4）此时aj即为a1, a2, ..., an的最大公约数。

本文提供了两个版本的JavaScript代码来求解公倍数和公约数，重点在于算法逻辑的实现，因此命名较为简化，多使用单字母变量。

简单易懂的循环实现

0. 简单易懂的循环实现

function getMin(arr){
  var min = Infinity
  arr.forEach(function(item){
    if( item < min && item !=0 ){
      min = item
    }
  })
  return min
}
function howMuchZero(arr){
  var zerocount = 0
  arr.forEach( function(item){
    item === 0 ?
    zerocount++ : zerocount
  }
    )
  if(zerocount === arr.length -1) {
    return true
  }
  else return false
}
function maxDivi(arr){
  do {
  var min = getMin(arr)
  arr = arr.map((item)=> item===min? item:item%min
    )
  }
  while (!howMuchZero(arr))
  return getMin(arr)
}
function minMulti(arr){
  var totalMulti = arr.reduce((pre,item)=>
    pre = pre * item
    )
  var brr = arr.map((item)=>
    totalMulti/item
    )
  var brr_maxDivi = maxDivi(brr)
  return totalMulti/brr_maxDivi
}

函数嵌套函数的实现方式

1. 函数嵌套函数的实现方式

var arr_minMulti, arr_maxdivi
function minMulti(arr){
  var totalmulti =
    arr.reduce((multi,curvalue) => multi * curvalue)
  if (totalmulti === 0) {
    arr_minMulti = 0
    return
  }
  var marr = arr.map((item) => totalmulti/item)
  maxDivisor(marr)
   arr_minMulti = totalmulti / arr_maxdivi
}
function maxDivisor(arr){
  var min = getMin(arr)
  if(min === Infinity) {
    arr_maxdivi = min
    return
  }
  var exparr = arr.filter(function(item){
      return (item !== min && item !== 0)
  })
  if(exparr.length === 0){
    arr_maxdivi = min
    return;
  }
  else{
    var modearr = arr.map(function(item){
      return (item === min||item===0)? item:item%min
    })
    console.log(modearr,'modearr')
    maxDivisor(modearr)
  }
}
function getMin(arr){
  var min = Infinity
  arr.forEach(function(item){
    if (item && item < min) {
      min = item
    }
  })
  return min
}
arr =[13,20,10,26]
minMulti(arr)
console.log('最小公倍数',arr_minMulti)

面向对象（Object Oriented）的实现方式

2. 面向对象（Object Oriented）的实现方式

function maxDivisor(arr,origin){
  this.arr = arr
  this.min = this._getMin(arr)
  this.maxDivisor = this._getMaxDiv()
  if(origin){
    this.minMulti = this._getMinMulti()
  }
}
maxDivisor.prototype._getMin = function(arr) {
  var min = Infinity
  arr.forEach(item => min = (item && item < min)? item : min)
  return min
}
maxDivisor.prototype._getMaxDiv = function() {
  var arr_maxdivi
  var self = this,
    arr = this.arr
  function maxDivisor(arr){
    //console.log(self._getMin)
    var min = self._getMin.call(null,arr)
     console.log(min,'min')
    if(min === Infinity) {
      arr_maxdivi = 0
      return ;
    }
    var exparr = arr.filter( item => (item !== min && item != 0) )
    if(exparr.length === 0){
      arr_maxdivi = min
      return;
    }
    else{
      var modearr = arr.map(item =>
        (item === min || item === 0)? item : item % min
      )
      maxDivisor(modearr)
      }
  }
  maxDivisor(this.arr)
  return arr_maxdivi
}
maxDivisor.prototype._getMinMulti = function(){
  var arr = this.arr,
    arr_minMulti
  var totalmulti =
    arr.reduce((multi,curvalue) => multi * curvalue)
  if (totalmulti === 0) {
    return 0
  }
  else {
    var marr = arr.map((item) => totalmulti/item),
    b = new maxDivisor(marr,false)
    arr_minMulti = totalmulti / b.maxDivisor
    return arr_minMulti
  }
}
var a = new maxDivisor([12,9,6],true)
console.log(a)

附录：求多个数最小公倍数的变换算法原理分析

附录：求多个数最小公倍数的变换算法原理分析

记[a1, a2, ..., an]为a1, a2, ..., an的最小公倍数，(a1, a2, ..., an)为它们的最大公约数，其中a1, a2, ..., an为非负整数。对于两个数a和b，公式[a, b] = ab / (a, b)成立，因此两个数的最小公倍数可通过其最大公约数计算。然而，该关系不能简单推广至n个数，即[a1, a2, ..., an] = M / (a1, a2, ..., an)（M为所有数的乘积）并不总是成立。例如：[2, 3, 4]不等于24 / (2, 3, 4)。这说明两个数的最大公约数与最小公倍数关系无法直接扩展为n个数的情况。

本节探讨多个数最小公倍数与最大公约数之间的关系，尝试将两个数的关系扩展至n个数，并基于此利用求n个数最大公约数的向量变换算法来计算多个数的最小公倍数。

多个数最小公倍数和最大公约数之间的关系

1．多个数最小公倍数和多个数最大公约数之间的关系

设p为a1, a2, ..., an中一个或多个数的素因子，这些数关于p的指数分别为r1, r2, ..., rn。在r1, r2, ..., rn中，最大值为rmax（可能有多个数达到该最大值），最小值为rmin（可能有多个数达到该最小值）。例如：对于4, 12, 16，关于素因子2的指数分别为2, 2, 4，其中最大值出现1次，最小值出现2次；关于素因子3的指数分别为0, 1, 0，最大值出现1次，最小值出现2次。

对于最大公约数，其仅包含a1, a2, ..., an中共同拥有的素因子，且每个素因子的指数取这些数中该素因子的最低指数；若最低指数为0，则表示不包含该素因子[1]。

对于最小公倍数，其仅包含a1, a2, ..., an中出现过的所有素因子，且每个素因子的指数取这些数中该素因子的最高指数[1]。

定理1：[a1, a2, ..., an] = M / (M/a1, M/a2, ..., M/an)，其中M为a1, a2, ..., an的乘积，a1, a2, ..., an为正整数。

例如：对于4, 6, 8, 10，其最小公倍数[4, 6, 8, 10] = 120。而乘积M = 4 * 6 * 8 * 10 = 1920。根据公式计算：M / (M/a1, M/a2, ..., M/an) = 1920 / (6*8*10, 4*8*10, 4*6*10, 4*6*8) = 1920 / 16 = 120。

证明过程如下：

在序列M/a1, M/a2, ..., M/an中，素因子p的指数均大于等于r1 + r2 + ... + rn - rmax，且存在项使得p的指数等于r1 + r2 + ... + rn - rmax。原因如下：

（1）M/ai中p的指数为r1 + r2 + ... + rn - ri，因此M/a1, M/a2, ..., M/an中p的最小指数为r1 + r2 + ... + rn - rmax。

（2）对于a1, a2, ..., an中p指数最大的项aj（可能有1项或多项），M/aj中p的指数为r1 + r2 + ... + rn - rmax。

或者，对于a1, a2, ..., an中p指数最大的项aj，M/aj中p的指数小于等于M/ak（其中ak为除aj外的其他n-1个项之一），且M/aj中p的指数确实为r1 + r2 + ... + rn - rmax。

因此，(M/a1, M/a2, ..., M/an)中p的指数为r1 + r2 + ... + rn - rmax，从而M / (M/a1, M/a2, ..., M/an)中p的指数为rmax。

上述推导中的p未受任何限制。由于a1, a2, ..., an包含的所有素因子在M / (M/a1, M/a2, ..., M/an)中均表现为最高指数，故公式[a1, a2, ..., an] = M / (M/a1, M/a2, ..., M/an)成立。

得证。

当n=2时，定理1退化为[a, b] = ab / (ab/a, ab/b) = ab / (b, a) = ab / (a, b)。因此，定理1是两数最小公倍数公式[a, b] = ab / (a, b)的推广。利用定理1，可将求多个数的最小公倍数转化为求多个数的最大公约数。

多个数最大公约数的算法实现

2．多个数最大公约数的算法实现

根据定理1，求多个数最小公倍数可转化为求多个数的最大公约数。传统求多个数最大公约数(a1, a2, ..., an)的方法是多次求两个数的最大公约数，即：

（1）使用辗转相除法[2]计算a1和a2的最大公约数(a1, a2)；

（2）使用辗转相除法计算(a1, a2)和a3的最大公约数，得到(a1, a2, a3)；

（3）使用辗转相除法计算(a1, a2, a3)和a4的最大公约数，得到(a1, a2, a3, a4)；

（4）依此类推，直到求得(a1, a2, ..., an)。

上述传统方法需要进行n-1次辗转相除运算。

本文将两数的辗转相除法扩展为n数的情况，即通过一次n数辗转相除计算最大公约数。基本方法是用最小数模其他数，依据是定理2。

定理2：对于多个非负整数a1, a2, ..., an，若aj > ai（i不等于j），则在序列中用aj - ai替换aj，其最大公约数不变，即(a1, a2, ..., aj-1, aj, aj+1, ..., an) = (a1, a2, ..., aj-1, aj-ai, aj+1, ..., an)。

例如：(34, 24, 56, 68) = (34, 24, 56-34, 68) = (34, 24, 22, 68)。

证明过程如下：

根据最大公约数的交换律和结合律，有：

(a1, a2, ..., aj-1, aj, aj+1, ..., an) = ((ai, aj), (a1, a2, ..., ai-1, ai+1, ..., aj-1, aj+1, ..., an))（当i>j时），或者

(a1, a2, ..., aj-1, aj, aj+1, ..., an) = ((ai, aj), (a1, a2, ..., aj-1, aj+1, ..., ai-1, ai+1, ..., an))（当i<j时）。

而对于(a1, a2, ..., aj-1, aj-ai, aj+1, ..., an)，有：

(a1, a2, ..., aj-1, aj-ai, aj+1, ..., an) = ((ai, aj-ai), (a1, a2, ..., ai-1, ai+1, ..., aj-1, aj+1, ..., an))（当i>j时），或者

(a1, a2, ..., aj-1, aj-ai, aj+1, ..., an) = ((ai, aj-ai), (a1, a2, ..., aj-1, aj+1, ..., ai-1, ai+1, ..., an))（当i<j时）。

因此，只需证明(ai, aj) = (ai, aj-ai)即可。

由于(aj-ai) = aj-ai，因此ai和aj的任意公因子必然也是(aj-ai)的因子，即也是ai和(aj-ai)的公因子。又因aj = (aj-ai) + ai，所以ai和(aj-ai)的任意公因子必然也是aj的因子，即也是ai和aj的公因子。因此，ai和aj的最大公约数与ai和(aj-ai)的最大公约数相等，即(ai, aj) = (ai, aj-ai)成立。

得证。

定理2类似于矩阵的初等变换，即：

定义向量的最大公约数为该向量各分量的最大公约数。对向量<a1, a2, ..., an>进行变换：在一个分量中减去另一个分量，新向量与原向量的最大公约数相等。

求多个数最大公约数采用反复用最小数模其他数的方法，即对其他数用最小数多次相减，直到得到比最小数更小的余数。设n个正整数为a1, a2, ..., an，求多个数最大公约数的算法描述如下：

（1）找到a1, a2, ..., an中的最小非零项aj，若有多个最小非零项则任取一个；

（2）将aj以外的所有其他非零项ak用ak mod aj代替；若没有除aj以外的其他非零项，则转到（4）；

（3）回到步骤（3）（注：原文此处可能有误，应为回到步骤1或类似逻辑，但按原文保留）；

（4）a1, a2, ..., an的最大公约数为aj。

例如：对于5个数34, 56, 78, 24, 85，有：

(34, 56, 78, 24, 85) = (10, 8, 6, 24, 13) = (4, 2, 6, 0, 1) = (0, 0, 0, 0, 1) = 1，

对于6个数12, 24, 30, 32, 36, 42，有：

(12, 24, 30, 32, 36, 42) = (12, 0, 6, 8, 0, 6) = (0, 0, 0, 2, 0, 6) = (0, 0, 0, 2, 0, 0) = 2。

多个数最小共倍数的算法实现

3. 多个数最小共倍数的算法实现

求多个数最小共倍数的算法步骤如下：

（1）计算m = a1 * a2 * ... * an；

（2）将a1, a2, ..., an中的所有项ai用m/ai代换；

（3）找到a1, a2, ..., an中的最小非零项aj，若有多个最小非零项则任取一个；

（4）将aj以外的所有其他非零项ak用ak mod aj代替；若没有除aj以外的其他非零项，则转到（6）；

（5）回到步骤（3）；

（6）最小公倍数为m/aj。

上述算法已在VC环境下使用高级语言编程实现，并通过多组求5个随机数最小公倍数的实例与标准方法进行了比较，验证了其正确性。标准计算方法为：求5个随机数最小公倍数需通过求4次两个数的最小公倍数获得，而两个数的最小公倍数通过求两个数的最大公约数获得。

5. 结论

计算多个数的最小公倍数是常见的基本运算。n个数的最小公倍数可以表示为另外n个数的最大公约数，因此可以通过求多个数的最大公约数来计算。求多个数最大公约数可采用向量转换算法一次性求得。

PS：这里再为大家推荐一款本站相关在线工具供大家参考：

在线最小公倍数/最大公约数计算工具： http://tools.jb51.net/jisuanqi/gbs_gys_calc

更多关于JavaScript相关内容感兴趣的读者可查看本站专题：《JavaScript数学运算用法总结》、《JavaScript数据结构与算法技巧总结》、《JavaScript数组操作技巧总结》、《JavaScript事件相关操作与技巧大全》、《JavaScript操作DOM技巧总结》及《JavaScript字符与字符串操作技巧总结》

希望本文所述对大家JavaScript程序设计有所帮助。