时间戳

首页 > 解决方案 > 由于数字太大而无法处理而导致无限循环

javascript - 由于数字太大而无法处理而导致无限循环

问题描述

https://www.freecodecamp.org/learn/coding-interview-prep/project-euler/problem-5-smallest-multiple

我正在解决 Project Euler，这是我为第 5 个问题提出的解决方案。它通过了前 5 个测试用例，但在最后一个测试用例中失败了。smallestMult(20)

我相信它正在发生，因为当n>=17. （它在这里的代码片段中工作没有问题）

function smallestMult(n) {
  let num = n
  let count = n

  while(true){
    num = num + n
    for(let i = n; i>0; i--){
      if(num%i==0){
        count = count - 1
      }
      if(count==0){
        return num
      }
    }
    count = n
  }
}
console.log(smallestMult(20));

关于如何改进的任何想法？

标签： javascriptalgorithm

解决方案

您的解决方案有效，但是效率较低。你可以试试这个方法：

function smallestMult(n) {
  let index = 1;
  let lcm= 1;
  // Loop until the last number
  while(index != n+1){
    // Get lcm of index and previous lcm
    lcm = findLcm(lcm,index)
    // Increment Index
    index++
  }
  return lcm
}

function findLcm(n1,n2){
let hcf;
// looping from 1 to number1 and number2 to find HCF
for (let i = 1; i <= n1 && i <= n2; i++) {
    // check if is factor of both integers
    if( n1 % i == 0 && n2 % i == 0) {
        hcf = i;
    }
}
// find LCM
let lcm = (n1 * n2) / hcf;
return lcm
}

console.log(smallestMult(24))
console.log(smallestMult(17))
console.log(smallestMult(29))

推荐阅读