Project Euler 50: Consecutive prime sum

Question

I just finished solving Project Euler's 50th problem, but it's awfully slow. I'd like to hear your thoughts on my code's efficiency and practices.

Problem Statement

The prime 41, can be written as the sum of six consecutive primes:

\$41 = 2 + 3 + 5 + 7 + 11 + 13\$

This is the longest sum of consecutive primes that adds to a prime below one-hundred.

The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.

Which prime, below one-million, can be written as the sum of the most consecutive primes?

Code

---

let primeNumbers = [];

function isPrime(number) { // checks whether number is prime or not
    for(let i = 2; i <= number / 2; i++) { // stops checking at 1/2 of number
        if (number % i === 0) return false;
    }
    return true;
}

function storePrimes(count) {
    for(let i = 2; i < count; i++) { // starts at 2
        if (isPrime(i)) {
            primeNumbers.push(i);
        }
    }
}

function findLargestSum() {
    let termsCount = 0;
    let sumOfTerms = 0;

    primeNumbers.forEach(currentSum => { // keeps track of possible sum
        primeNumbers.forEach((startNumber, startIndex) => { // keeps track of start index
            let consecutiveCount = 0;
            let consecutiveSum = 0;
            primeNumbers.forEach((prime, primeIndex) => { // iterates through primes
                if (primeIndex >= startIndex) { // applies start index
                    consecutiveCount++;
                    consecutiveSum += prime;
                    if (consecutiveCount > termsCount && consecutiveSum === currentSum) {
                        termsCount = consecutiveCount;
                        sumOfTerms = consecutiveSum;
                    }
                }
            })
        })
    })

    return {largestSum: sumOfTerms, termsCount: termsCount};
}

function findPrimes(count) {
    storePrimes(count)
    let results = findLargestSum();
    console.log("Largest sum'o'primes of prime consecutives under " + count + " is: " + results.largestSum + " with " + results.termsCount + " terms.");
}

findPrimes(1000000);

Answer 1

Improvement in function isprime:

for(let i = 2; i <= number / 2; i++)

can be

for(let i = 2; i <= Math.round(Math.sqrt(number)) + 1 ; i++)

Otherwise, the best easy to understand approach(in accordance to my knowledge) is to use the Sieve of Eratosthenes. Your problem can be a subset of the following problem Sieve of Eratosthenes JavaScript implementation - performance very slow over a certain number. Credits of the code below goes to the owner of this post.

function getPrimesUnder(number) {
  var start = new Date().getTime();

  var numbers = [2];
  var sqNum = Math.sqrt(number);
  var i, x;
  for (i = 3; i < number; i = i + 2) {
    numbers.push(i);
  }
  for (x = 0; numbers[x] < sqNum; x++) {
    for (i = 0; i < numbers.length ; i++){
       if (numbers[i] > numbers[x]) {
        if(numbers[i] % numbers[x] === 0){
          numbers.splice(i, 1)
        }
      }
    }
  }
  var end = new Date().getTime();
  var time = end - start;
  alert('Execution time: ' + time/1000 + ' seconds');
  return numbers;

} 

There is something much more efficient (Which is the fastest algorithm to find prime numbers?) known as Sieve of Atkin. You can do more research on it.

Answer 2

You should measure the duration of each step in the algorithm to detect where the bottleneck(s) is/are. You can do that using console.time("id") paired with console.timeEnd("id"):

function findPrimes(count) {
    console.time("prime generation");
    storePrimes(count);
    console.timeEnd("prime generation")
    console.time("finding");
    let results = findLargestSum();
    console.timeEnd("finding");
    console.log("Largest sum'o'primes of prime consecutives under " + count + " is: " + results.largestSum + " with " + results.termsCount + " terms.");
}

You'll then detect that storePrimes() takes considerably long time to generate primes up to 1,000,000.

---

One optimization could be in isPrime():

function isPrime(number) {
  if (number < 2) return false;
  if (number == 2) return true;
  if (number % 2 == 0) return false;

  let sqrt = Math.round(Math.sqrt(number));

  for (let n = 3; n <= sqrt; n += 2) {
    if (number % n == 0) return false;
  }

  return true;
}

As seen it is only necessary to check for values up to and including the square root of the number. And by handling 2 as a special case you only need to check odd numbers from 3 and up.

But storePrimes() is still too slow, and I think it's about that you constantly push new primes on primeNumbers. Instead you can use a generator function in the following way:

function* createPrimes(limit) {
  yield 2; 
  for (let i = 3; i < limit; i += 2) { // You can start at 3 and only iterate over odd numbers
    if (isPrime(i)) {
      yield i;
    }
  }
}

and then in findPrimes() call it as:

function findPrimes(limit) {
  primeNumbers = Array.from(createPrimes(limit));
  let results = findLargestSum(limit);
  console.log("Largest sum'o'primes of prime consecutives under " + limit + " is: " + results.largestSum + " with " + results.termsCount + " terms.");
}

This will speed up the process beyond compare. Notice that I've changed some names like count to limit because it determines the largest prime - not the number of primes to generate.

---

Using forEach() in this exact situation isn't a good idea, because you can't step out whenever you like, but have to iterate the entire prime set over and over again unnecessarily in your three nested loops. That is very inefficient. Besides that, I find it rather difficult to read and understand nested forEach()-calls as in your code.

Instead you should use good old for-loops, because you then can break out when ever the state makes it meaningless to continue the loop:

function findLargestSum() {
  let termsCount = 0;
  let sumOfTerms = 0;
  let length = primeNumbers.length;

  for (let i = 0; i < length; i++) {
    let targetSum = primeNumbers[i]; // keeps track of possible sum

    for (var j = 0; j < i && i - j > termsCount; j++) {
      let sum = 0;
      for (var k = j; k < i && sum < targetSum; k++) {
        sum += primeNumbers[k];
      }

      if (k - j > termsCount && sum == targetSum) {
        termsCount = k - j;
        sumOfTerms = targetSum;
      }
    }
  }

  return { largestSum: sumOfTerms, termsCount: termsCount };
}

This is a significant improvement on performance, but is still rather slow. I have tried different steps to optimization, but I can't point out the bottlenecks. But below is my take on the challenge:

function findLargestSum(limit) {
  let resultSum = 0;
  let resultCount = -1;

  for (var i = 0; i < primeNumbers.length && primeNumbers.length - i > resultCount; i++) {
    let sum = 0;

    for (var j = i; j < primeNumbers.length; j++) {
      let prime = primeNumbers[j];

      sum += prime;
      if (sum >= limit) {
        sum -= prime;
        break;
      }
    }
    j--;


    while (j >= i && !isPrime(sum)) {
      sum -= primeNumbers[j--];
    }

    if (j >= i && j - i > resultCount) {
      resultSum = sum;
      resultCount = j + 1 - i;
    }
  }

  return { largestSum: resultSum, termsCount: resultCount };
}

It repeatedly sums up the primes from each prime in the list and backtracks by subtracting the largest prime until the sum is either a prime or zero. It continues as long as the number of primes beyond i is greater than the length of an already found sequence.

Answer 3

Consider what you are doing here. You are generating a list of primes less than a number. You are generating this list in order of increasing size. One simple optimization is to seed the list with a few primes at the beginning. In particular, 2 and 3. Then you iterate to skip over all the even numbers. That cuts your checks in half.

Now, a second point is that you don't have to divide by all numbers less than half the number. You only have to divide by primes less than the square root of the number. And you know what, you have a list of primes smaller than the number. So use that in your trial division.

So in your prime generation function (what you call storePrimes but which I might call load_primes), call a function that divides by the primes that you already have.

function is_divisible_from(candidate, numbers) {
    for (const n of numbers) {
        if (candidate % n === 0) {
            return true;
        }

        if (n > candidate / n) {
            return false;
        }
    }

    // you should never get here
    return false;
}

It is quite common to generate both the remainder and the quotient at the same time. So both candidate % n and candidate / n can be generated by one activity in many parsers. So this is probably efficient (do timing tests if you want to be sure). You have to do the division/remainder operation once per loop regardless. This just uses both results where most alternatives are doing an added square root check (hopefully just once).

This is essentially saying that if you can find some number in the list that divides the candidate, then it is clearly a composite number and not prime. I call this is_divisible_from as better describing what the function does. But when you use it, a true result means that the number is not prime and a false result that it is.

function load_primes(upper_bound) {
    let primes = [ 2, 3 ];

    for (let i = 5; i <= upper_bound; i += 2) {
        if (!is_divisible_from(i, primes)) {
            primes.push(i);
        }
    }
}

There's also another optimization here, but I doubt that it will give enough savings to overcome its increased overhead. It's possible to skip over all the divisible by three values.

Now you have efficiently created a list of primes in \$\mathcal{O}(n \sqrt{n})\$ time, where \$n\$ is your upper bound. Your original was \$\mathcal{O}(n^2)\$ in that step. Your original was also \$\mathcal{O}(p^3)\$ to use the list where \$p\$ was the number of primes. But I believe that it is possible to do this in \$\mathcal{O}(p^2)\$ time.

It should be obvious that you can calculate the sums in linear time. So keep adding to the sum until it is too large (greater than the upper bound). Then subtract the smallest value from it until is both small enough and prime. It's linear to check if a given number is prime (in the list). And it's linear to generate the sums, because we don't need to check every pair of indexes. We iterate over each left once and each right once.

let primes = load_primes(upper_bound);
let left = 0;
let right = 0;
let sum = 2;
let result = {largestSum: sum, termsCount: 0};

while (right < primes.length && left <= right) {
    if ((right - left > result.termsCount) && (0 <= primes.indexOf(sum))) {
        result.largestSum = sum;
        result.termsCount = right - left;
    }

    right++;
    sum += primes[right];
    while ((sum > upper_bound) && (left < right)) {
        sum -= primes[left];
        left++;
    }
}

result.termsCount++;
return result;

This works because we are looking for consecutive primes. So we don't need to backtrack or compare most values. We can move forward through all the possibilities that might be true, looking at a sliding window of values.