Problem 7

10001st prime

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
What is the 10 001st prime number?

https://projecteuler.net/problem=7

Brute Force

Let’s add to the 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
  }

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

  return {
    primesTo : primesTo,
    nPrimes : nPrimes
  }
})();

function euler7() {
  var primes = Primes.nPrimes(10001);
  return primes[10000];
}
timer(euler7);
// euler7 x 1: 28.311ms
// 104743