I've been playing around with Haskell and find it fascinating, especially the Lazy Evaluation feature, which allows us to work with (potentially) infinite lists.
From this, derives the beautiful implementation of the Sieve of Eratosthenes to get an infinite list of primes:
primes = sieve [2..]
where
sieve (x:xs) = x : sieve [i | i <- xs, i `mod` x /= 0]
Still using Haskell, I can have either:
takeWhile (<1000) primes
which gives me the primes until 1000 (n), or
take 1000 primes
which gives me the first 1000 primes
I tried to implement this in Javascript, forgetting the 'infinite' possibility and this is what i came up with:
const sieve = list => {
if (list.length === 0) return []
const first = list.shift()
const filtered = list.filter(x => x % first !== 0)
return [first, ...sieve(filtered)]
}
const getPrimes = n => {
const list = new Array(n - 1).fill(null).map((x, i) => i + 2)
return sieve(list)
}
It works perfectly (if I don't reach maximum call stack size first), but I can only get the prime numbers "up until" n.
How could i use this to implement a function that would instead return "the first n" primes?
I've tried many approaches and couldn't get it to work.
Bonus
is there any way I can use tail call optimization or something else to avoid Stack Overflows for large Ns?
As of ECMAScript 2025 we have some iterator helper methods, including filter, take and toArray which come in handy here:
function* eratosthenes(sieve=from(2)) {
const prime = sieve.next().value;
yield prime;
yield* eratosthenes(sieve.filter(candidate => candidate % prime));
}
function* from(i) {
while (true) yield i++;
}
// Demo
console.log(eratosthenes().take(100).toArray());