javascript - 优化(CodeWars 整数 : Recreation One)

Question

我设法为 this CodeWars challenge 找到了两个算法.不幸的是，它们不够快(> 12000 毫秒)。

关于如何改进我的代码有什么建议吗？

v1:

const listSquared = (m, n) => {
  const result = [];
  for (let i = m; i <= n; i++) {
    const divisorsOfi = [];
    for (let j = 0; j <= i; j++) {
      if (i % j === 0) {
        divisorsOfi.push(Math.pow(j, 2))
      }
    }
    let sumOfDivisorsOfi = 1;
    if (divisorsOfi.length > 1) {
      sumOfDivisorsOfi = divisorsOfi.reduce((a, b) => a + b);
    }
    if (Number.isInteger(Math.sqrt(sumOfDivisorsOfi))) {
      result.push([i, sumOfDivisorsOfi]);
    }
  }
  return result;
}

v2:

const listSquared = (m, n) => {
  const result = [];
  for (let i = m; i <= n; i++) {
    let sumOfSqrtDivisorsOfi = divisors(i);
    if (Number.isInteger(Math.sqrt(sumOfSqrtDivisorsOfi))) {
      result.push([i, sumOfSqrtDivisorsOfi]);
    }
  }
  return result;
}

const divisors = (n) => [...Array(n + 1).keys()].slice(1)
.reduce((s, a) => s + (!(n % (a)) && Math.pow(a, 2)), 0);

Answer 1

我以v1为基础，修改如下

const listSquared = (m, n) => {
  const result = [];
  for (let i = m; i <= n; i++) {
    const divisorsOfi = [];
    for (let j = 0; j <= Math.sqrt(i); j++) {
      if (i % j === 0) {
        divisorsOfi.push(Math.pow(j, 2));
        if (i/j != j)
          divisorsOfi.push(Math.pow(i/j, 2));

      }
    }
    let sumOfDivisorsOfi = 1;
    if (divisorsOfi.length > 1) {
      sumOfDivisorsOfi = divisorsOfi.reduce((a, b) => a + b);
    }
    if (Number.isInteger(Math.sqrt(sumOfDivisorsOfi))) {
      result.push([i, sumOfDivisorsOfi]);
    }
  }
  return result;
}

这里的想法很简单:如果a可以被j整除那么它也可以被a/j整除所以我们只需要检查 sqrt(a) 第一个数字。唯一需要注意的是，如果 a/j 和 j 是相同的数字，则计算结果两次。