Robert Eisele
Engineer, Systems Architect and DBA

Project Euler 10: Summation of primes

Problem 10

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

Solution

This problem is a good example for a sieve approach. A function I use quite often from my library is the following Sieve of Eratosthenes. The implementation is straightforward, but it gives the inverse. All primes are marked with 0! The reason is, we can construct the array with Uint8Array, so we save memory and it's initialized with 0 already, which saves the initial fill operation.

function sieve(n) {

  var data = new Uint8Array(n + 1);
  data[0] = 1;
  data[1] = 1;
  var bound = Math.floor(Math.sqrt(n));
  for (var i = 2; i <= bound; i++) {

    if (data[i] === 0) {
      for (var j = i + i; j <= n; j+= i) {
        data[j] = 1;
      }
    }
  }
  return data;
}

In order to complete the task we could loop again over the array and sum all non-primes. The result would then be the sum of all numbers minus the sum of all non-primes:

\[\sum\limits_{i=1}^n i - s = \frac{n(n+1)}{2} -s\]

As we already know what primes are, we can use the function above as a template to save these extra roundtrips, by calculating it inline:

function solution(n) {

  var sum = 1;
  var data = new Uint8Array(n + 1);
  data[0] = 1;
  data[1] = 1;
  var bound = Math.floor(Math.sqrt(n));
  for (var i = 2; i <= bound; i++) {

    if (data[i] === 0) {
      for (var j = i + i; j <= n; j+= i) {
        if (data[j] === 0) {
          data[j] = 1;
          sum+= j;
        }
      }
    }
  }
  return n * (n + 1) / 2 - sum;
}

There are still couple improvements we can make: We don't need to remember all odd numbers all the time and as we need the sum, we can work into that direction as well to save some iterations:

function solution(n) {

  var sum = 0;
  var bound = (Math.sqrt(n + 1) - 1) >> 1;
  n = n >> 1;

  var data = new Uint8Array(n + 1);

  for (var i = 1; i <= bound; i++) {

    for (var j = i * 2 * (i + 1); j <= n; j+= 2 * i + 1) {

      if (data[j] === 0) {
        data[j] = 1;
        sum+= j * 2 + 1;
      }
    }
  }
  return 2 + n * (n + 1) + n - sum;
}
solution(2e6 - 1);

Go to overview