Problem 10

Summation of primes

The sum of the primes below is .
Find the sum of all the primes below two million.

 https://projecteuler.net/problem=10

Brute Force

This is pretty straight forward with our primes generator from problem 3.

var Primes = (function() {
  // Returns if n is prime using trial division for previously found primes.
  // Only check up to floor(sqrt(n)).
  function isPrime(n, primes) {
    var pi = 1, // Skip checking if divisible by 2.
        prime = primes[pi],
        limit = Math.floor(Math.sqrt(n));
    while (prime <= limit) {
      if (!(n % prime)) return false;
      prime = primes[++pi];
    }
    return true;
  }

  function primesTo(n) {
    var primes, i = 1;
    if (n < 2) return [];
    if (n === 2) return [2];
    if (n === 3) return [2, 3];
    primes = [2, 3];
    while (true) {
      var candidate = 6 * i - 1;
      if (candidate > n) break;
      if (isPrime(candidate, primes)) primes.push(candidate);
      candidate += 2;
      if (candidate > n) break;
      if (isPrime(candidate, primes)) primes.push(candidate);
      i++;
    }
    return primes
  }

  return {
    primesTo : primesTo
  }
})();

function euler10() {
  return Primes.primesTo(2000000).reduce(function(n, sum) {
    return n + sum;
  }, 0);
}
timer(euler10);
// euler10 x 1: 779.420ms
// 142913828922