This Laziness in Python - Computerphile video presents this program to produce primes with generators:
def nats(n):
yield n
yield from nats(n+1)
def sieve(s):
n = next(s)
yield n
yield from sieve(i for i in s if i%n!=0)
p = sieve(nats(2))
next(p) # 2
next(p) # 3
next(p) # 5
next(p) # 7
next(p) # 11
I decided to implement this sieve-algorithm using JavaScript generators. I'm pretty confident with JavaScript in general but have never worked with generators directly before.
Here's what I have so far:
function* nextNaturalNumber(n) {
yield n;
yield* nextNaturalNumber(n + 1);
}
function* sieve(n) {
let count = 0;
let g = nextNaturalNumber(2);
while (count++ < n) {
const possiblePrime = g.next().value;
yield possiblePrime;
// here's where I'm stuck:
// how can I filter the values from the nextNaturalNumber-generator stream that are not divisible by 2?
}
}
// print the first 10 primes
for (const prime of sieve(10)) {
console.log(prime);
}
As mentioned in the code-comment, I'm stuck on how to filter the values from the generator stream that are not divisible by 2 and thus performing the "sieve"-operation. Is there a simple way to do this (as in Python with yield from sieve(i for i in s if i%n !=0)
) in JavaScript?
Unfortunately, Javascript does not have that many good iterator operations. You can, however, just make a filter function that loops through the iterator and yield values that match:
function* nextNaturalNumber(n) {
// switch to iterative to avoid stack overflows
while(true) {
yield n;
n ++;
}
}
function* filterIter(iter, pred) {
for (const item of iter) {
if (pred(item)) {
yield item;
}
}
}
function* sieve(n) {
let count = 0;
let g = nextNaturalNumber(2);
while (count++ < n) {
const possiblePrime = g.next().value;
yield possiblePrime;
g = filterIter(g, v => v % possiblePrime != 0);
}
}
// print the first 10 primes
for (const prime of sieve(10)) {
console.log(prime);
}