I was working on a code challenge with the following description:

Given an array of positive or negative integers

I= [i1,..,in]

you have to produce a sorted array P of the form

[ [p, sum of all ij of I for which p is a prime factor (p positive) of ij] ...]

Example: I = [12, 15]; //result = [[2, 12], [3, 27], [5, 15]]

So I created an algorithm that does exactly that, but I have some performance issues. On the code challenge website (Codewars), my algorithm times out for fairly large integers, 173471 being a specific example.

One issue I am aware of with the algorithm and want to improve is that my current method for generating primes simply takes the largest number in the input array, and generates primes up to that number, but rarely do I need that many primes. I have not found a full proof way of creating the full list of possible primes otherwise, however. A second issue is that I have a loop running within my loop, to check which numbers in the input have factors in the list of primes I generated. If I could somehow reduce it to one loop, that would reduce the complexity.

Anyway all of that aside, here is my algorithm:

// Function that returns a collection of primes up to a given number
const sieveOfEratosthenes = (int) => {
  // Initialize some values
  const primes = [...Array(int + 1).keys()].slice(2);
  const sqrtCeil = Math.sqrt(int);
  let p = primes[0];
  let pIndex = 0;
  let factor = 2;

  // Until index refers to the last element, sieve primes
  while (primes[pIndex] < sqrtCeil) {
    const productIndex = primes.indexOf(factor * p);

    if (productIndex > -1) {
      primes.splice(productIndex, 1);
    }

    factor += 1;

    if (factor * p > primes[primes.length - 1]) {
      factor = 2;
      pIndex += 1;
      p = primes[pIndex];
    }
  }

  return primes;
};

function sumOfDivided(lst) {
  // If the input is empty, return an empty list
  if (lst.length === 0) {
    return [];
  }

  // Generate primes with a ceiling of the highest number in the input,
  // accounting for negative numbers
  const primes = sieveOfEratosthenes(
    Math.max(...lst.map((int) => (int < 0 ? int * -1 : int)))
  );

  // Reduce primes array to array of tuples, value one being being the prime,
  // value two being the sum of numbers it was a prime factor for in the input
  return primes.reduce((acc, prime) => {
    // Initialize values
    let sum = 0;
    let primeFactorCount = 0;

    // Check if each integer in the input had this prime as a factor
    for (let int of lst) {
      if (prime > int && int > 0) {
        continue;
      }

      if (int % prime === 0) {
        sum += int;
        primeFactorCount += 1;
      }
    }

    // If at least one number matched, add the tuple to the array
    if (primeFactorCount > 0) {
      return [...acc, [prime, sum]];
    }

    return acc;
  }, []);
}
```