Sum by Prime Factors not efficient enough, pass tests but fails attempt

Question

So, the exercise gives us an array of numbers (lst) and we have to return an array (ans) of arrays, the arrays inside ans have to include one prime and a sum of all numbers (from lst) of which the prime number is factor of. This is the link for the codewars kata: https://www.codewars.com/kata/54d496788776e49e6b00052f/train/javascript

The problem comes when I fail the attempts bc of ineficciency in the code, as right now it works at O(n^2), so when the test try a huge number, it fails.

I've been trying to implement new ways of getting the prime factors but I can't seem to find any ways of rewritting it.

I just want tips to make it better, not the answer itself!!

This is my code:

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

This is some nice code but it needs some work. I tried putting it into codewars but the problem wasn't the time, but the result it was giving. It has some flaws in its calculations.

Flaws

The problems present in your algorithm are:

• For your upper limit in the Eratosthenes function you use the last element of I. However, it's not stated that I is sorted but that P(the result) should be. Therefore you may need a linear search to find the max value in the given array. Now it's very important to not search for the max number but for the number with the max absolute value, so that you can account for negative integers.
• The second problem which I found was the fact that the sieve of Eratosthenes wasn't checking if the upper limit(n) was a prime, and didn't include it in its results. This can cause some problems as for example eratosthenes(3) will return [2] whereas it should return [2, 3].

Time Optimisations

When it comes to making your algorithm faster there is mainly one thing that slows it down drastically. That is the unnecessary checking for primes which do not divide any element of I in the first 2 for loops. This of course can be done within the third and fourth for loops. All you need is a boolean to make sure at one point the prime divided one of the numbers and if it did not then do not push it to the ans array. Therefore, with some small changes to the 3rd and 4th for loops you can completely omit the first 2 as they become unnecessary.

However, your solution even without this optimisation seems to pass all tests if implemented correctly.