质因数求和不够有效，通过测试但尝试失败

Question

因此，练习给了我们一个数字数组（lst），我们必须返回一个数组数组（ans），ans 内的数组必须包含一个素数以及所有数字（来自 lst）的和，其中素数为数是 的因数。 这是 codewars kata 的链接：https://www.codewars.com/kata/54d496788776e49e6b00052f/train/javascript

当我因代码效率低下而尝试失败时，问题就出现了，因为现在它的工作时间为 O(n^2)，所以当测试尝试大量时，它会失败。

我一直在尝试实现获取素因数的新方法，但我似乎找不到任何重写它的方法。

我只是想要一些让它变得更好的技巧，而不是答案本身！！

这是我的代码：

function sumOfDivided(lst) {
  //your code
  let prime = eratosthenes(lst[lst.length - 1])
  let ans = [];
  for (let i = 0; i < prime.length; i++){
    let count = 0;
    for (let j = 0; j < lst.length; j++){
      if (lst[j] % prime[i] !== 0){
        count += 1
      }
    }
    if (count === lst.length){
      prime.splice(i, 1)
      i--
    }
  }
  console.log(prime)
  for (let i = 0; i < prime.length; i++){
    let curr = [];
    let sum = 0;
    for(let j = 0; j < lst.length; j++){
      if (lst[j] % prime[i] === 0){
        sum += lst[j]
        }
      }
    ans.push([prime[i], sum])
    }
  return ans;
}

var eratosthenes = function(n) {
    let array = [];
    let upperLimit = Math.sqrt(n);
    let output = [];
    for (let i = 0; i < n; i++) {
        array.push(true);
    }
    for (let i = 2; i <= upperLimit; i++) {
        if (array[i]) {
            for (let j = i * i; j < n; j += i) {
                array[j] = false;
            }
        }
    }
    for (let i = 2; i < n; i++) {
        if(array[i]) {
            output.push(i);
        }
    }

    return output;
};

Answer 1

这是一些不错的代码，但还需要一些工作。我尝试将其放入代码战中，但问题不在于时间，而在于它给出的结果。它的计算存在一些缺陷。

缺陷

您的算法中存在的问题是：

• 对于埃拉托斯特尼函数中的上限，您使用 I 的最后一个元素。但是，并没有说明 I 已排序，但 P（结果）应该如此。因此，您可能需要线性搜索来查找给定数组中的最大值。现在非常重要的是不要搜索最大数字，而是搜索具有最大绝对值的数字，这样您就可以考虑负整数。
• 我发现的第二个问题是埃拉托斯特尼筛法没有检查上限（n）是否是素数，并且没有将其包含在结果中。这可能会导致一些问题，例如

  eratosthenes(3)

  将返回

  [2]

  ，而它应该返回

  [2, 3]

  。

时间优化

当谈到让你的算法更快时，主要有一件事会大大减慢它的速度。这是对素数的不必要检查，这些素数不会在前 2 个 for 循环中整除 I 的任何元素。这当然可以在第三个和第四个 for 循环中完成。您所需要的只是一个 boolean 来确保素数在某一点除以其中一个数字，如果没有，则 not 将其推入

ans

数组。因此，通过对第三个和第四个 for 循环进行一些小的更改，您可以完全省略前两个，因为它们变得不必要。

但是，即使没有这种优化，如果实施正确，您的解决方案似乎也能通过所有测试。