JavaScript - 欧拉计划#5——效率

Question

这是 Euler 项目的问题 #5。

任务是找到能被数字 1-20 整除的最小数字。我的代码似乎适用于 1-18，但在 19 时我的浏览器开始超时。这让我相信我的代码效率低下。

我该如何缓解这种情况？

function divisible(a){
    counter = 0;
    result = 2;
    while (counter < a){
        for (var x = 0; x <= a; x ++){
            if (result % x === 0){
                counter ++;
            }
        }
        if (counter != a){
            counter = 0;
            result ++;
        }
    }
    return result;
}
divisible(20)

Answer 1

基本上，您需要 least common multiple共 1,...,20。

我将使用 gcd 实现 lcm ，可以使用快速 Euclidean algorithm 来实现.

function gcd(a, b) {
  return b === 0 ? a : gcd(b, a%b); // Euclidean algorithm
}
function lcm(a, b) {
  return a * b / gcd(a, b);
}
function divisible(a){
  var result = 1;
  for(var i=2; i<=a; ++i)
    result = lcm(result, i);
  return result;
}
divisible(20); // 232792560