Skip to content

Instantly share code, notes, and snippets.

@erwinv
Last active July 18, 2022 03:00
Show Gist options
  • Save erwinv/521af9e455bf6f1399244cc7fa88ffa0 to your computer and use it in GitHub Desktop.
Save erwinv/521af9e455bf6f1399244cc7fa88ffa0 to your computer and use it in GitHub Desktop.
twinPrimes = filter twin (zip primes (tail primes))
twin (x,y) = y == x+2
primes = sieve [2..]
sieve (p:ps) = p : sieve [x | x <- ps, mod x p /= 0]
function* naturalNumbers(from = 1) {
let n = from;
while (true) {
yield n++;
}
}
function* primes() {
// yield* sieveRecursive(naturalNumbers(2)); // call stack overflows
yield* sieveIterative(); // no stack overflow, even better performance
}
function* sieveRecursive(xs) {
const nextPrime = xs.next().value;
yield nextPrime;
// stack overflows because of the recursive filters
// (1 filter added to the stack for every new prime number)
yield* sieveRecursive(filter(x => x % nextPrime !== 0, xs));
}
function* sieveIterative() {
const primes = [];
for (const x of naturalNumbers(2)) {
if (every(
p => x % p !== 0,
takeWhile(p => p <= Math.floor(Math.sqrt(x)), primes)
))
{
primes.push(x);
yield x;
}
}
}
function every(predicate, xs) {
for (const x of xs) {
if (!predicate(x)) return false;
}
return true;
}
function* filter(predicate, xs) {
for (const x of xs) {
if (predicate(x)) {
yield x;
}
}
}
function* twinPrimes() {
const areTwins = ([x, y]) => y === x + 2
yield* filter(areTwins, zip(primes(), tail(primes())))
}
function* tail(xs) {
xs.next();
yield* xs;
}
function* zip(xs, ys) {
for (const x of xs) {
const {done, value: y} = ys.next();
if (done) return;
yield [x, y];
}
}
function* take(n, xs) {
if (n <= 0) return;
let i = 0;
for (const x of xs) {
yield x;
if (++i >= n) return;
}
}
function* takeWhile(predicate, xs) {
for (const x of xs) {
if (!predicate(x)) return;
yield x;
}
}
function main() {
// for (const n of primes()) {
// console.log(n);
// }
for (const twins of twinPrimes()) {
console.log(twins);
}
}
main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment