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