I initially came here for the discussion on recursion, but stumbled upon an excellent solution provided by Thankyou using some clever abstractions.
The approach utilized in that response involved a variation of the Sieve of Eratosthenes. However, I'd like to introduce an alternate version of this sieve which may lack elegance but offers improved performance.
Here is the primary implementation as a generator function:
const sieve = function * () {
const C = {} // store known composite numbers
let q = 2
while (q < Infinity) {
if (C [q]) {
C [q] .forEach (n => C [n + q] = [... (C [n + q] || []), n] )
delete C [q]
} else {
C [2 * q] = [q]
yield q
}
q += 1
}
}
The traditional Sieve method involves eliminating all multiples of a prime number. While this works well with predefined lists of numbers, we need to handle continuous streams without a fixed upper limit. Therefore, instead of crossing off all multiples at once, we only eliminate the next multiple to be encountered. This is tracked using the local variable C, which contains information about prime multiples.
For instance, if we reach a test value of 11, we have already identified primes such as 2, 3, 5, and 7. The subsequent multiple of 2 is 12; for 3, it's also 12, followed by 15 for 5 and 14 for 7. At this stage, C will appear as shown below:
{
12: [3, 2],
14: [7],
15: [5]
}
If 11 does not exist in this list, we include 2 * 11 in C and yield it as the next prime. So, when assessing 12, C updates to:
{
12: [3, 2],
14: [7],
15: [5],
22: [11]
}
Since 12 is now part of this object, it is deemed non-prime. Subsequently, adjustments must be made. Removing 12 from the list necessitates placing our 2 and 3 values on their succeeding multiples. For example, following 12, the next multiple of 2 is
14</code, so we update the value at <code>14
to contain
2. Similarly, after
12, the subsequent multiple of
3 is
15, prompting us to amend the value at
15</code to involve <code>3.
As a result, when we encounter 13, C appears as:
{
14: [7, 2],
15: [5, 3],
22: [11]
}
Given that 13 is absent in C, we identify it as prime, yielding it and adding 26 (2 * 13) to
C</code alongside the value <code>13
. This process leads to an ongoing sequence of prime numbers, maintaining the collection of each prime's upcoming multiples.
An astute observer might notice some excess activity within this methodology. Specifically, when introducing the initial multiple of, say, 7 to our list, commencing at
14</code isn't essential since it's already marked off as a multiple of <code>2
. Likewise,
21 represents a multiple of
3,
28 is tied to
4 (and consequently
2),
35 is linked to
5, followed by
42</code denoting a multiple of <code>6
(including
2 and
3). The first specific multiple that requires verification is
49 whenever a new prime like
p is added; the initial relevant multiple is
p ** 2. One can rectify this quirk by replacing:
C [2 * q] = [q]
with:
C [q * q] = [q]
To validate this function, one may execute tests as follows:
const iterator = sieve()
console.log(iterator.next()) //=> {value: 2, done: false}
console.log(iterator.next()) //=> {value: 3, done: false}
console.log(iterator.next()) //=> {value: 5, done: false}
console.log(iterator.next()) //=> {value: 7, done: false}
console.log(iterator.next()) //=> {value: 11, done: false}
console.log(iterator.next()) //=> {value: 13, done: false}
One could implement a take function akin to the one found in Thankyou's explanation, which is likely the optimal approach. Alternatively, you can modify this function to terminate either after finding the first n primes or upon exceeding the value of n.
The latter option merely entails incorporating the parameter max and substituting instances of Infinity accordingly. Conversely, the former scenario presents a slightly greater challenge. Here is one iteration of this concept:
const sieve = function * (count) {
const C = {} // known composite numbers
let n = 0
let q = 2
while (n < count) {
if (C [q]) {
C [q] .forEach (n => C [n + q] = [... (C [n + q] || []), n] )
delete C [q]
} else {
C [q * q] = [q]
n += 1
yield q
}
q += 1
}
};
console .log ([... sieve(1000)])
.as-console-wrapper {max-height: 100% !important; top: 0}
In a more logical context, our internal composites data structure should ideally abandon Object mappings in favor of integer-to-integer array conversion. A more suitable alternative would entail utilizing a Map conforming to integers paired with Sets of integers. Such an implementation is feasible:
const sieve = function * (count) {
const C = new Map () // known composite numbers
let n = 0
let q = 2
while (n < count) {
if (C .has (q)) {
[... C .get (q)] .forEach (
n => C .set (n + q, (C .get (n + q) || new Set ()) .add (n))
)
C .delete (q)
} else {
C .set (q * q, new Set ([q]))
n += 1;
yield q
}
q += 1
}
};
Although somewhat less readable compared to its Object-Array counterpart, this implementation operates identically. Performance assessments are pending, though no significant speed variations are anticipated when transitioning between structures. Regardless, both methods remain effective.
This narrative deviates from my typical style. Although steering clear of inner structure mutations via recursive means is plausible, no readily apparent technique comes to mind.
Additional insights into this rendition of the Sieve, along with discussions on its relative complexity, can be explored within Melissa E. O’Neill's exceptional piece titled The Genuine Sieve of Eratosthenes. Although academically inclined, the paper retains readability and comprehension, particularly for those familiar with Haskell.