cf.completefrontend
MATH & GEOMETRY · CORE

Sieve of Eratosthenes

Find every prime number up to n by crossing out the multiples of each prime, starting from 2.

Time O(n log log n)Space O(n)3 practice problemsStep-through picture

The idea

A prime number is a whole number above 1 whose only divisors are 1 and itself: 2, 3, 5, 7, 11, .... Checking one number for primality means trying divisors. Checking every number up to a million that way repeats a lot of work.

The sieve does it all at once. Write down every number from 2 to n, all marked as possibly prime. Take the first one, 2: it's prime. Cross out its multiples, 4, 6, 8, ..., since they have 2 as a divisor. The next number not crossed out, 3, is prime. Cross out its multiples. Keep going. Whatever survives is prime.

Two shortcuts make it fast. Crossing out for prime p can start at p * p, because smaller multiples like 2p and 3p were already crossed out by smaller primes. And you can stop once p * p > n, because every number left by then is prime.

An everyday example

Picking out the team captains in a lineup

Numbered players stand in a long line. The first player who isn't sitting down becomes a captain, and every player whose number is a multiple of the captain's number sits down. Then the next player still standing becomes a captain, and their multiples sit down. Once you pass the square root of the last number, nobody new needs to sit. Everyone still standing is a captain: a prime.

How the example maps to the code
In the exampleIn the code
The line of players, all standingisPrime = new Array(n + 1).fill(true)
The next player still standing becomes captainif (!isPrime[p]) continue;
The captain's multiples sit downisPrime[multiple] = false
Starting with the captain's own squaremultiple = p * p
Everyone still standingthe primes list

From the slow way to sieve of eratosthenes

  1. Start with the obvious way: for each number m from 2 to n, try dividing it by every d with d * d <= m. If nothing divides it, it's prime. Up to one million, that takes about 67.7 million divisions, and most of them are spent proving again and again that numbers like 999,999 are not prime.
  2. Turn the question around. Instead of asking every number "what divides you?", let each prime announce its own multiples. The multiples of 2 are 4, 6, 8, ...: you can reach them by adding 2 again and again, with no division at all. Each one gets crossed out with a single array write.
  3. Which numbers get to announce? Walk from left to right. The first number not yet crossed out must be prime: if it had a smaller prime factor, that prime would already have crossed it out. So the walk finds the primes in order, and only primes ever do the crossing out.
  4. Two savings finish it. A prime p can start crossing out at p * p, because smaller multiples like 2p and 3p were crossed out by smaller primes. And once p * p > n, every composite up to n is already gone. Keep a true/false array isPrime, run p while p * p <= n, and collect what survives. That loop is the Sieve of Eratosthenes.

How it works

  1. Make an array isPrime of n + 1 entries, all true, then set isPrime[0] and isPrime[1] to false.
  2. Loop p from 2 while p * p <= n.
  3. If isPrime[p] is false, p was crossed out by a smaller prime, so skip it.
  4. Otherwise p is prime. Cross out its multiples starting at p * p, stepping by p.
  5. After the loop, every index still true is a prime. Collect them into primes.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function primesUpTo(n) {
  2. const isPrime = new Array(n + 1).fill(true);
  3. isPrime[0] = false;
  4. isPrime[1] = false;
  5. for (let p = 2; p * p <= n; p++) {
  6. if (!isPrime[p]) continue;
  7. for (let multiple = p * p; multiple <= n; multiple += p) {
  8. isPrime[multiple] = false;
  9. }
  10. }
  11. const primes = [];
  12. for (let i = 2; i <= n; i++) {
  13. if (isPrime[i]) primes.push(i);
  14. }
  15. return primes;
  16. }

How fast it is

TimeO(n log log n)
Extra memoryO(n)

Each prime p crosses out about n / p entries, and the sum of those over all primes is n log log n. The array has one entry per number up to n.

  • Best caseO(n log log n)

    Every n does the same kind of work: the loops depend only on n, not on any data. A small n like 40 just means fewer steps.

  • Average caseO(n log log n)

    Prime p writes about n / p entries, and adding that up over all primes up to √n gives about n log log n. For n = 1,000,000 it makes about 2.1 million writes.

  • Worst caseO(n log log n)

    Large n. The log log n part grows so slowly (about 2.6 for a million) that the time is close to linear, so memory, not time, is usually the limit.

Common mistakes

  • Starting the inner loop at 2 * p instead of p * p. The answer is still right, but it does extra work.
  • Looping p up to n instead of p * p <= n. Still correct, but slower.
  • Forgetting to mark 0 and 1 as not prime, so they show up in the answer.
  • Using the sieve for a single number near a billion. A billion-entry array is far too big; trial division up to √n is better for one check.

When to use it

Look for these clues in a problem:

  • The problem needs many primes, or primality checks for many numbers up to some limit.
  • The limit is known in advance and fits in memory, such as up to a few million.
  • You need counts or lists of primes in a range.
  • Repeated trial division would be too slow for the number of checks asked.

Check yourself

Answer each one in your head first, then open it.

Why does 7 never cross anything out when n = 40?

Its first multiple to cross out would be 49, which is past 40. Every smaller multiple of 7, such as 14 or 35, has a smaller prime factor that already crossed it out.

What goes wrong if the loop runs while p * p < n and n = 49?

The loop stops at p = 6, so 7 never crosses out 49, and 49 is reported as prime.

Why is the first true entry after a prime always another prime?

If it were composite, its smallest prime factor would be smaller than it, and that prime would already have crossed it out.

How many entries does isPrime need for n = 100, and why?

101, for indexes 0 to 100, so that isPrime[100] exists and the index equals the number.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 3 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The sieve keeps one rule: when the outer loop reaches p, every composite number whose smallest prime factor is below p has been crossed out, and no prime has been crossed out. At the start, p = 2, and there are no primes below 2, so the rule holds.

Each step keeps the rule. If isPrime[p] is still true, then p has no prime factor below p, so it is prime. Its inner loop crosses out p * p, p * p + p, and so on: each is p times a number of at least p, so each is composite, and no prime is lost. Every composite whose smallest prime factor is exactly p is at least p * p, so all of them are crossed out now. If isPrime[p] is false, p is composite and has nothing new to cross out.

The outer loop ends once p * p > n, after about √n values of p. At that point, take any composite m <= n. Its smallest prime factor q has q * q <= m <= n, so q < p, and by the rule m is already crossed out. So every index still true is prime, and the final loop collects exactly the primes.

Going deeper

3 more ideas

Why crossing out can start at p * p

Every multiple of p smaller than p * p is p × k with k < p. Such a k has a prime factor smaller than p, and that prime already crossed out p × k. So the first multiple that might still be standing is p × p.

Why you can stop when p * p > n

A number m <= n that isn't prime is a × b with a <= b, so a × a <= m <= n. Its smallest prime factor is at most a, so it was crossed out while p * p <= n. Nothing that survives past that point can be a composite number.

Its speed and memory

Each prime p crosses out about n / p numbers. Adding n/2 + n/3 + n/5 + ... over the primes gives O(n log log n), which grows almost like n. The array needs n + 1 entries, so for very large n a Uint8Array saves memory compared with a normal array of booleans.

Work it by hand

Every step in a table, with why

Find every prime up to 40. The trace shows two skipped values of p and the loop stopping before 7 crosses anything out.

n = 40

Steppp * pCrossed out (new ones)What happensWhy
1---isPrime has 41 entriesEvery entry starts true, then isPrime[0] and isPrime[1] are set to false.
2244, 6, 8, ..., 40 (19)2 is prime: cross outisPrime[2] is still true, so 2 is prime. It crosses out every even number from 4 to 40.
3399, 15, 21, 27, 33, 39 (6)3 is prime: cross outIt visits 11 multiples from 9 to 39, but 12, 18, 24, 30, and 36 were already crossed out by 2. Only 6 are new.
4416-isPrime[4] is false: skip4 was crossed out by 2, so it isn't prime. Its multiples are multiples of 2, already gone.
552525, 35 (2)5 is prime: cross outIt starts at 25, not 10: 10, 15, and 20 were crossed out by 2 and 3. It visits 25, 30, 35, 40; only 25 and 35 are new.
6636-isPrime[6] is false: skip36 <= 40, so the loop still runs for 6, but 6 was crossed out and is skipped.
7749-49 > 40: loop ends7 is prime, but every multiple of 7 below 49 (14, 21, 28, 35) already has a smaller prime factor. Nothing is left for 7 to do.
8---collect the true entriesThe last loop walks from 2 to 40 and pushes every index still marked true.

It returns the 12 primes 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, after 34 array writes in total. Primes like 11 and 37 were never visited by the crossing-out loops at all; they simply survived.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Sieve of EratosthenesO(n log log n)O(n)You need all primes up to n, or many primality answers for numbers up to about 10^7.
Trial division for every numberO(n √n)O(1)Almost never for a whole range: up to a million it does about 67.7 million divisions, against the sieve's 2.1 million writes.
Trial division for one numberO(√n)O(1)You only need to test one or a few numbers, even large ones near 10^12, where a sieve array would be far too big.
Linear sieveO(n)O(n)You also want each number's smallest prime factor, or you want a guaranteed single write per composite.

Extra memory: O(n): one entry per number from 0 to n. A Uint8Array uses 1 byte per entry, so one million numbers fit in about 1 MB; a normal array of booleans uses more.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Sieve of Eratosthenes and the other approaches, on a scale where each line up is 10 times more steps.
  • Sieve of Eratosthenes O(n log log n)
  • Trial division for every number O(n √n)
  • Trial division for one number O(√n)
  • Linear sieve O(n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Sieve of Eratosthenes173,3174 million
Trial division for every number3231,6231 billion
Trial division for one number3321,000
Linear sieve101,0001 million

Inputs that need care

5 tricky inputs
n = 0 or n = 1
The outer loop doesn't run (4 > 1), the collecting loop finds nothing, and it returns []. That's right: there are no primes below 2.
n = 2
The outer loop doesn't run, but the collecting loop finds isPrime[2] still true, so it returns [2].
n is a prime's square, like 49
When p = 7, 7 * 7 <= 49 is true, so 49 is crossed out. With p * p < n instead, 49 would wrongly be reported as prime.
A negative or decimal n, like -5 or 10.5
new Array(n + 1) throws a RangeError: Invalid array length. Guard with if (n < 2) return [] and round the input down first.
A huge n, like one billion
The array alone needs a billion entries, too much for a browser tab. Sieve in fixed-size windows (a segmented sieve), or use trial division if you only need to test a few numbers.

Variations and follow-ups

Twists interviewers add

Smallest prime factor sieve

Instead of true/false, store in spf[m] the first prime that crossed m out. Then any m <= n can be factorized by dividing by spf[m] again and again, in O(log m) steps. This is the fast way to factorize many small numbers.

Segmented sieve

To find primes between L and R when R is huge but R - L is small, first sieve the primes up to √R. Then use them to cross out multiples inside a window array of size R - L + 1 only. Memory depends on the window, not on R.

Odd numbers only

Every even number above 2 is composite, so store only odd numbers: index i stands for 2i + 1. That halves both the memory and the writes, at the cost of a little index arithmetic.

Linear sieve

Euler's version crosses out each composite exactly once, by its smallest prime factor, giving O(n) time. It also fills the smallest-prime-factor table for free. In practice it's rarely much faster, because log log n is already tiny.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "count the primes less than n", "list all primes up to", or many questions about the primality or factors of numbers up to a fixed limit. A single number to test points to trial division instead.
  • Explain it as: "Each prime crosses out its multiples starting at its square. Whatever is never crossed out is prime. I stop when p * p > n." Then state the cost, O(n log log n) time and O(n) memory.
  • Test n = 0, n = 2, and a square of a prime like n = 25 or 49. The square catches the classic < versus <= mistake.
  • Expect the follow-up "what if n is a billion?" Answer with the segmented sieve, or note that a single number only needs trial division up to √n.

Where frontend code uses it

The same idea in real UI code
  • Precomputing a table once at startup and then answering many questions from it is the same trade the sieve makes: memory for speed. Lookup tables for icons, emoji, or locale data in apps work the same way.
  • Educational math apps and number-puzzle games in the browser use sieves to find primes instantly as the user moves a slider.
  • Some string hash functions multiply by a prime such as 31, and Java's String.hashCode is a well-known example. Prime lists from a sieve help when choosing such constants.

Related algorithms