质数因子分组求和代码性能优化咨询（Codewars Kata）

题目要求：给定数字数组lst，返回二维数组ans，ans的每个子数组包含一个质数，以及lst中所有能被该质数整除的数的总和。

我的代码能通过测试，但时间复杂度为O(n²)，处理大规模数据时会超时，无法完成正式提交。尝试优化质数因子的获取逻辑但没有思路，仅需要优化建议，不需要完整代码。

我的代码如下：

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;
};

优化建议 #

• 修正埃氏筛的上限：当前用数组最后一个元素作为筛的上限是错误的——数组中可能存在绝对值更大的元素（比如数组是[15, 3]），应该取数组元素的最大绝对值作为筛的上限，否则会漏掉大的质因数。
• 反转处理逻辑：不要先生成所有质数再过滤，改为遍历数组中的每个数，分解其唯一质因数，然后将该数累加到对应质因数的总和中。这样避免处理大量与数组元素无关的质数，大幅减少循环次数。
• 高效分解质因数：对每个数先取绝对值（正负不影响整除性），分解时只保留唯一的质因数（比如12只需要记录2和3，不需要重复记录），避免重复累加。
• 避免低效的数组修改：不要用splice原地修改质数数组，改用filter生成新数组，避免数组重排带来的性能损耗。
• 优化筛的范围：如果分解质因数时遇到大于sqrt(max_abs)的数，且该数不为1，那么它本身就是质数，需要直接加入质因数列表。

内容的提问来源于stack exchange，提问作者AlejandroCRG