最小公倍数 - for 循环中断 - javascript

Question

我正在上 FreeCodeCamp.org 的课程，作业是找到 "Smallest Common Multiple"。所以我想出了一个我认为可行的解决方案，并且在一定程度上做到了。然后代码就像它正在崩溃一样。这是我的代码：

function smallestCommons(arr) {
  arr = arr.sort((a,b) => {return a - b;});
  console.log(arr);
  var truesec = false;
  for(var a = arr[1]; truesec != true; a++){

    for(var e = 1; e <= arr[1]; e++){
      //console.log(a % e + " " + e);
      if(a % e != 0){
        truesec = false;
        break;
      }else{
        truesec = true;
      }
    }
    //console.log(truesec + " " + a);
    if(truesec == true){
      return a;
    }
  }

  return a;
}


console.log(smallestCommons([23,18]));

根据他们的清单，这应该 return 6056820 但每次我检查都会得到不同的结果我从同一个中得到了 114461 和 122841代码。有人可以告诉我这有什么问题吗？

如果有帮助，请看作业： Intermediate Algorithm Scripting: Smallest Common Multiple

Answer 1

您的算法试图做的是找到 1 和数组中较大数字之间的公倍数，这可能需要很长时间。但是FreeCodeCamp的题目要求你求数组中两个数的公倍数，所以你的算法计算出的结果与测试不符

要使您的解决方案有效，您可以更改

来自 for (var e = 1; e <= arr[1]; e++)

到for (var e = arr[0]; e <= arr[1]; e++)

为了在数组中的两个数字之间循环。

Answer 2

我会采取不同的方法来解决这个问题：

创建函数以获取所有质因数
创建a[0]和a[1]
将数组缩减为每个质因数的最大幂。
乘以数组中剩余的所有质因数

当 k 是答案时，您的方法将采用 O(k*a[1]) - k 可能非常高...此方法将采用 O((a[1])^2)

考虑以下代码：

function smallestCommons2(arr) {
    arr.sort((a,b) => {return a - b;});
    let factors = [];
    for(let i = arr[0]; i <= arr[1]; i++)
        factors.push(findPrimeFactors(i));

    let reduced = reduceFactors(factors);
    let ans = 1;
    for (let i in reduced)
        ans *= Math.pow(i, reduced[i]);
    return ans;
}

function reduceFactors(factorsArr) {
    let factorObject = {};
    for (let i in factorsArr) {
        for(let key in factorsArr[i]) {
            if (!(key in factorObject) || factorObject[key] < factorsArr[i][key])
                factorObject[key] = factorsArr[i][key];
        }
    }
    return factorObject;
}

function findPrimeFactors (num) {
    var primeFactors = [];
    while (num % 2 === 0) {
        primeFactors.push(2);
        num = num / 2;
    }

    var sqrtNum = Math.sqrt(num);
    for (var i = 3; i <= sqrtNum; i++) {
        while (num % i === 0) {
            primeFactors.push(i);
            num = num / i;
        }
    }
    if (num > 2)
        primeFactors.push(num);

    let factorObject = {};

    for (let item of primeFactors) {
        if (item in factorObject)
            factorObject[item] += 1;
        else factorObject[item] = 1;
    }
    return factorObject;
}


console.log(smallestCommons2([23,18]));

此代码将在

秒内输出 6056820

已编辑 - 发现以更好的方式做同样的事情

最小公倍数 - for 循环中断 - javascript

Least Common Multiple - for loop breaks down - javascript

javascript

loops

for-loop

function

lcm