Javascript for loop 在计算 LCM 时出现无限循环错误

Question

我要解决的问题是计算给定数字范围的最小公倍数。数组中提供的数字可以按任何顺序排列，但 attay 将只有两个数字。

我的代码适用于 [1,5] 、 [1,10]、[1,12] 对，但是一旦我尝试 [1,13] 我就会遇到无限循环错误并且答案变得不确定。

对于以下代码，预期答案是 360360

function smallestCommons(arr) {

  var a     = arr[0];
  var b     = arr[1];
  var start = 0;
  var end   = 0;
 
  if (a<b) {
    start=a;
    end=b;
  }
  else {
    start=b;
    end=a;
  }

  //console.log("Start:"+start);
  //console.log("End:"+end);

  var numArray = [];
  for(let i=start; i<end+1; i++) {
    numArray.push(i);
  }

  console.log(numArray);
  
  var oddArray = [];
  var product  = numArray.reduce((a,b)=>a=a*b);
  
  console.log("Product:"+product);
  console.log(numArray[0]);
  
  var result = 0;
  
  console.log(result);

  //let j=numArray[0];

  for(let j=numArray[0];j<=product;j++) {
    var count = 0;
    for(let k=0;k<numArray.length; k++) {
  
      if(j%numArray[k]==0) {
        count++;
      }
    }
    if(count==numArray.length) {
      return j;
    }
  }
}

console.log(smallestCommons([1,13]));

Answer 1

它应该是 product.length-1 因为 reduce returns 一个数组

for(let j=numArray[0];j<=product.length-1;j++) {

Answer 2

你的做法是错误的。

1、2、3、4的LCM是多少？它是 12，因为它是 3 x 4。

您的代码将做什么：

var product  = numArray.reduce((a,b)=>a=a*b); // product will be 24
...
for(let j=numArray[0];j<=product;j++) { // iterate from 1 -> 24
    var count = 0;
    for(let k=0;k<numArray.length; k++) { // iterate from 0 -> 3
  
      if(j%numArray[k]==0) { // consider it a hit if j is divisible by an element
        count++;
      }
    }
    if(count==numArray.length) { // on the 4th "hit"
      return j; // return j which is a number between 1 -> 24
    }
  }

如果您运行陷入无限循环，那是因为您没有获得正确的点击次数。

解决 LCM 问题的正确方法是考虑质因数。让我们再次使用 1、2、3、4。

对于每个数字，我得到一个质因数。

1 -> 1(1)
2 -> 2(1), 1(1)
3 -> 3(1), 1(1)
4 -> 2(2), 1(1)

我们通过对每个素因子使用 max(cnt) 来减少这个集合。 1的最大计数是1。2的最大计数是2。3的最大计数是1。所以我们然后去：2 x 2 x 3 = 12，这就是我们的答案。

这需要 2 遍：

首先遍历数字数组。
第二次通过素数计数图。

Answer 3

...我的方式：

function isPrime(n)
  {
  if(n < 2) return false
  for (let x = 2; x < n; ++x) if (n%x===0) return false
  return true
  }
 
function smallestCommons(range)
  {
  let nMin = Math.min(...range)
    , nTab = []
    , xPow = {}
    ;
  for (let n = Math.max(...range); n >1; --n)
    {
    if (n>=nMin && !(nTab.find(x=>(x%n===0))) ) nTab.push(n)
    if (isPrime(n))
      {
      nTab.forEach(v=>
        { 
        if(v%n===0)
          {
          let p = 0
          while ((v%(n**++p))===0) {}
          --p
          if ( !xPow[n] ) xPow[n] = p
          else xPow[n] = Math.max(xPow[n], p)
          }
        })
      }
    }
  return Object.entries(xPow).reduce((a,[v,p])=>a*(v**p),1)
  }    
 
console.log ('[1,4] ->', smallestCommons([1,4]) )
console.log ('[1,5] ->', smallestCommons([1,5]) )
console.log ('[1,10] ->', smallestCommons([1,10]) )
console.log ('[1,12] ->', smallestCommons([1,12]) )
console.log ('[1,13] ->', smallestCommons([1,13]) )

Javascript for loop 在计算 LCM 时出现无限循环错误

Javascript for loop giving infinite loop error while calculating LCM

javascript

algorithm

for-loop

infinite-loop

lcm