Sieve of Eratosthenes

sieveOfEratosthenes.js

/**
 * Initializes an empty sieve
 *
 * @returns {{primes: Set<number>, crossed: Set<number>, greatestComputedMultiples: Map<number, number>}}
 */
const createSieve = () => ({
    primes: new Set(),
    crossed: new Set(),
    greatestComputedMultiples: new Map(), // `prime` -> greatest computed multiple for `prime`
});

/**
 * Generates prime numbers < max that have not yet been computed in the
 * specified `cache`. That way, we can resume execution after the latest
 * computed prime number found in `cache` simply by calling the generator
 * again with a greater value of `max` and using the same reference to `cache`.
 *
 * @param max
 * @param cache
 * @returns {Generator<number, void, *>}
 */
const primes = function* (
    max,
    cache = createSieve(),
) {
    const {
        primes,
        crossed,
        greatestComputedMultiples,
    } = cache;

    for (let i = 2; i < max; i++) {
        if (!crossed.has(i) && !primes.has(i)) {
            primes.add(i);
            yield i;
        }

        let multiple = greatestComputedMultiples.get(i) || i;
        do {
            multiple += i;
            crossed.add(multiple);
            greatestComputedMultiples.set(i, multiple);
        } while (multiple < max);
    }
};

/**
 * Computes the n-th prime number.
 *
 * @param n
 * @param bufferSize
 * @param sieve
 * @returns {number}
 */
const nthPrime = (
    n,
    bufferSize = 100,
    sieve = createSieve(),
) => {
    let i = 1;
    while (i < n) {
        for (let prime of primes(bufferSize, sieve)) {
            if (i++ === n) {
                return prime;
            }
        }

        // update the search range if the n-th prime number has not been found at this point
        bufferSize += bufferSize;
    }
};

Usage:

const arr = [...primes(600)];
console.log(arr); // => [ 2, 3, 5, ..., 599 ]
console.log(arr[99]); // => 541
console.log(nthPrime(100)); // => 541
console.log(nthPrime(100_000)); // => 1299709