Skip to content

Instantly share code, notes, and snippets.

@CrossEye
Last active December 7, 2020 21:49
Show Gist options
  • Save CrossEye/e81013fe5dd4f4d036b855e14b1f78d3 to your computer and use it in GitHub Desktop.
Save CrossEye/e81013fe5dd4f4d036b855e14b1f78d3 to your computer and use it in GitHub Desktop.
Sieve of Eratosthenes
// all primes
const sieve = function * () {
const C = {}
let q = 2
while (true) {
if (C [q]) {
C [q] .forEach (n => C [n + q] = [... (C [n + q] || []), n] )
delete C[q]
} else {
C [q * q] = [q]
yield q
}
q += 1
}
};
// primes between `lo` (inclusive) and `hi` (inclusive)
const sieve = function * (lo, hi) {
const C = {}
let q = 2
while (q <= hi) {
if (C [q]) {
C [q] .forEach (n => C [n + q] = [... (C [n + q] || []), n] )
delete C[q]
} else {
C [q * q] = [q]
if (q >= lo) {
yield q
}
}
q += 1
}
};
// primes up to `hi` (inclusive)
const sieve = function * (hi) {
const C = {}
let q = 2
while (q <= hi) {
if (C [q]) {
C [q] .forEach (n => C [n + q] = [... (C [n + q] || []), n] )
delete C[q]
} else {
C [q * q] = [q]
yield q
}
q += 1
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment