javascript - 在除数数组中找到最小公约数

Question

我有一道 javascript 数学题:

我有除数数组:

var 除数 = ["3","4","5","10","12","15","20","30","60"]

以及在其中一项中无需提醒即可划分的项目数:

var items_to_divide = ["10","30"]

我正在寻找一个函数，它可以从 items_to_divide 之间的除数列表 (var divisors) 中给出最小公约数。

在这个例子中，结果应该是 5，因为 10/5 = 2 和 30/5 = 6 所以 5 是最小公分频器，因为它们都被 5 除以而没有提醒。

谁能在这里提出一个好的逻辑？

Answer 1

我建议执行以下步骤:

1. 对除数数组进行升序排序
2. 在这个数组上循环
3. 检查当前除数是否除以所有要除的项
4. 如果是，这是最低公分频器。

这个算法的一个实现可能是这个:

function best_divisor() {
  var division;

  // Sort divisor array from lowest value to highest one
  divisors = divisors.sort(function(a,b) {return +a > +b;});

  // Test each value of this array
  for (var i=0; i<divisors.length; i++) {
    divide = true;

    // check if it divides all values from the items_to_divide
    for (var j=0; j<items_to_divide.length; j++) {
      division = items_to_divide[j] / divisors[i];
      if(division !== Math.round(division)) {
        divide = false;
        break;
      }
    }

    // If all divisions give integers, this divisor is the lowest one
    if(divide) return divisors[i];
  }

  // No divisor found
  return -1;
}