Sieve of Eratosthenes

Medium TimeO(n log log n) SpaceO(n)

Given a limit n, return every prime from 2 up to and including n, in ascending order. 0 and 1 are not prime, so the answer starts at 2 and is empty for any n below it.

Examples

Example 1

Input
n = 30
Output
[2,3,5,7,11,13,17,19,23,29]
Ten primes up to 30. 30 itself is 2 × 3 × 5, so it is not one of them.

Example 2

Input
n = 7
Output
[2,3,5,7]
The limit is prime here, and it is in the answer.

The Code

function sieve(n) {
  const isComposite = new Array(n + 1).fill(false);
  const primes = [];
  for (let p = 2; p <= n; p++) {
    if (isComposite[p]) continue;
    primes.push(p);
    for (let multiple = p * p; multiple <= n; multiple += p) {
      isComposite[multiple] = true;
    }
  }
  return primes;
}
sieve(30);
Done

The first 12 calls, of 58. This one does not fit on a page.

Step through sieve(30) call by call

More like this

All math & numbers examples (8) →