What is the time complexity of the Sieve of Eratosthenes?

It runs in O(n log log n) time and uses O(n) space. The log log n factor comes from summing n/2 + n/3 + n/5 + ... over the primes up to n. That is far faster than testing each number for primality individually.

Why can you start crossing out multiples at p squared?

When you reach a prime p, every multiple of p smaller than p squared has already been crossed out by a smaller prime factor. For example, 2 times 3 was already removed when you sieved 2. So you can safely begin at p times p, which is the common optimisation.

No. A prime number has exactly two distinct positive divisors: 1 and itself. The number 1 has only one divisor, so it is neither prime nor composite. That is why the sieve treats 1 as a special case.

Where is the Sieve of Eratosthenes used?

It is the standard way to generate a table of all primes up to a limit, used in number-theory problems, competitive programming, cryptography pre-computation, and anywhere you need many primes quickly. For testing a single very large number, probabilistic tests like Miller-Rabin are used instead.

Vibe Engines is free, interactive AI engineering & system design — runs in your browser. Pick a learning path

ALGORITHMS · 07 / SIEVE OF ERATOSTHENES

Prime Time.

Q: What is the Sieve of Eratosthenes?

The Sieve of Eratosthenes is an ancient algorithm that finds all prime numbers up to a given limit. Starting from 2, it marks every multiple of each prime as composite; the numbers never crossed out are the primes. It uses only addition (counting in steps) and never tests divisibility, which makes it very fast.

Find every prime under 100 — without dividing a single time. Hit play and watch the multiples fall away. Whatever's left standing is prime.

THE GIST · 20 SECONDS

The Sieve of Eratosthenes finds primes by elimination. Start at 2 (the first prime) and cross out every multiple of 2. Jump to the next number still standing — 3 — and cross out its multiples. Repeat. The survivors are the primes. No division, no testing: just counting and crossing out. It's over 2,000 years old and still the fast way to list primes (O(n log log n)).

Primedivisible only by 1 and itself
Compositehas a smaller factor
Multiple2×n, 3×n, 4×n…
Sievecross out, keep the rest

Click the glowing number to cross out its multiples — or hit Play to auto-run.

UNDER THE HOOD

What you just played, written down

You crossed out multiples in waves until only primes were left. Here's the same idea as code.

How the sieve thinks — four moves

Assume everything's prime. List 2…N. (1 is a special case — neither prime nor composite.)
Find the next survivor. The smallest number not yet crossed out is the next prime, p.
Cross out its multiples. Mark 2p, 3p, 4p… as composite — they all have p as a factor, so none can be prime.
Repeat until p × p > N. Everything still standing is prime.

WHY IT'S FAST

It never divides. Crossing out the multiples of p is just counting in steps of p — pure addition. Summed over the primes, that's O(n log log n): barely more than linear.

The algorithm

function sieve(N):
    isPrime = [true] * (N + 1)
    isPrime[0] = isPrime[1] = false
    for p from 2 while p * p <= N:
        if isPrime[p]:                 # p survived → prime
            for m from p*p to N step p:
                isPrime[m] = false     # cross out multiples
    return [p for p in 2..N if isPrime[p]]

TIMEO(n log log n)counting, not dividing

SPACEO(n)one flag per number

THE p² SHORTCUT

Start crossing at p × p, not 2p: every multiple of p below p² (like 2×3) was already crossed out by a smaller prime. That's the one-line speed-up in the code above.

⚠ One is not prime

A prime has exactly two distinct divisors. 1 has only one, so it's neither prime nor composite — the sieve skips it.

↔ Its cousins

The segmented sieve handles huge ranges in chunks. The linear sieve hits O(n). For a single giant number, Miller–Rabin tests primality probabilistically.

★ Where it's used

Generating prime tables for number theory, competitive programming, and crypto pre-computation — anywhere you need lots of primes, fast.

The picture: who crosses out what

Every number from 2 to 50 appears exactly once. A composite is crossed out by its smallest prime factor; the first multiple that prime crosses out is its square, because every smaller multiple already has a smaller prime factor. After 7, nothing is left to cross.

Worked example, step by step

Sieve 2 to 100. For each prime p up to √100 = 10, cross out every multiple from p² upward. “Visited” counts every multiple the loop touches; “newly crossed” counts the ones that were still standing. The gap between them is wasted writes, numbers that a smaller prime had already removed.

Step	Starts at p²	Visited	Newly crossed	Already crossed	Candidates left
start	—	—	—	—	99
p = 2	4	49	49	0	50
p = 3	9	31	16	15	34
p = 5	25	16	6	10	28
p = 7	49	8	3	5	25
p = 11	121	—	—	—	25 (all prime)

Prime 2 removes 49 numbers, half of everything. By 7 the loop touches 8 multiples (49, 56, 63, 70, 77, 84, 91, 98) and only 3 are new: 49, 77 and 91 (7 × 7, 7 × 11, 7 × 13). The others, such as 56 = 7 × 8, were gone long before. Starting at p² instead of 2p is why: 7 × 2 through 7 × 6 each contain a prime smaller than 7, so they were already handled. At p = 11 the first useful multiple would be 121, which is past 100, so the sieve stops and 25 numbers remain. All of them are prime, with no division performed anywhere.

Complexity and trade-offs

Case	Time	Space	Why
Sieve of Eratosthenes	`O(n log log n)`	`O(n)`	For n = 1,000,000: 2,122,048 crossing-out writes, 78,498 primes found.
Trial division per number up to √k	`O(n √n)` worst	`O(1)`	Same range: 67,740,404 divisions testing each number in turn, about 32 times the sieve’s writes.
Linear sieve (Euler’s sieve)	`O(n)`	`O(n)` plus the prime list	Each composite is written exactly once: 921,501 writes for n = 1,000,000, instead of 2,122,048.
Segmented sieve	`O(n log log n)`	`O(√n + segment)`	Sieves a window at a time using the primes up to √n, so the range can be larger than memory or can start far from 0.
Bit-packed or odd-only sieve	`O(n log log n)`	`O(n / 8)` to `O(n / 16)` bytes	One bit per number or per odd number; for n = 10⁹ that is 125 MB instead of 1 GB for a byte array.

The sieve is cheap because its cost is a sum of n/p over primes p, and that sum grows like log log n, which is under 3 for any n a program will see. The trade-off is memory: the sieve needs a flag for every number up to n, so it answers “all primes up to n” very well and “is this one number prime?” poorly. For a single large number use a primality test; for a range far from zero use the segmented form. A Python list of booleans costs 8 bytes per entry on 64-bit CPython (a pointer), so for big n use bytearray.

Common mistakes

An off-by-one in the crossing-out range
Python’s range(p*p, n, p) stops before n. With n = 25 the multiples of 5 start at 25, which the range excludes, so the sieve returns 25 as a prime. It goes wrong whenever n is itself a multiple of a sieving prime. Use n + 1 as the end.
Treating 0 and 1 as prime
Initialising everything to True and only crossing out multiples leaves 0 and 1 standing. The sieve of 30 then returns [1, 2, 3, 5]… instead of starting at 2. Set both to False before the loop.
Starting the inner loop at 2p
The result is still correct, which makes it hard to notice. It is slower: at n = 1,000,000 the writes go from 2,122,048 to 2,197,839.
Looping the outer variable to n
Checking every p up to n instead of up to √n does 999,999 outer iterations instead of 999 at n = 1,000,000. The inner loops are empty beyond √n, so the output is identical and only the time is wasted.
Overflowing p * p
In a language with 32-bit integers, p * p <= n fails near the top of the range. For n = 2,147,483,647 and p = 46,341, the product should be 2,147,488,281 but wraps to -2,147,479,015, which is “less than n”, so the loop runs on and writes at a negative index. Compare p <= n / p or use 64-bit integers.

Where this shows up

Factoring many numbers: the smallest-prime-factor table
Record, for every composite, the prime that first crossed it out. Then any number up to n factors in one pass over that table: 360 gives 2 × 2 × 2 × 3 × 3 × 5. This is the standard tool when a problem asks about the factorisations of many numbers.
Counting primes
π(100) = 25, π(1,000,000) = 78,498, and there are 8,169 twin-prime pairs (p and p + 2 both prime) below 1,000,000. All three come from one array.
Number-theory problems and interviews
Count primes less than n is a classic interview question whose expected answer is exactly this sieve. Totients, divisor counts and Möbius values are computed by the same crossing-out loop with a different value stored per cell.
Cryptographic key generation
Code that searches for large random primes commonly discards candidates divisible by small primes before running a probabilistic test, and the small primes come from a sieve. The sieve finds the primes; the expensive test decides the survivors.

RUN IT YOURSELF

The Sieve, in Python & TypeScript

The same prime sieve in both languages, running for real in your browser — Python via WebAssembly, TypeScript transpiled on the fly. Switch tabs to compare them, read the numbered comments, edit anything, and hit Run (or ⌘/Ctrl + Enter).

HOW TO READ THE CODE — 4 IDEAS

Start by assuming every number is prime (then strike out 0 and 1) (step 1).
Walk p upward; you only need to reach √n (step 2).
For each surviving prime p, cross out its multiples, starting at p·p (step 3).
Whatever is still standing is prime (step 4).

CPython · WebAssembly

QUICK CHECK

Did it stick?

See every answer, with the reasoning

How does the sieve decide a number is composite?
Answer: It crosses it out as a multiple of a known prime — No division happens. A number is composite because it got crossed out while counting up the multiples of some prime.
After crossing out the multiples of every prime up to √N, the numbers still standing are…
Answer: all prime — Any composite ≤ N has a prime factor ≤ √N, so it was already crossed out. Whatever survives must be prime.
Is 1 a prime number?
Answer: No — it has only one divisor — A prime has exactly two distinct divisors (1 and itself). 1 has just one, so it is neither prime nor composite.

FAQ

The sieve, answered

What is the Sieve of Eratosthenes?

An ancient algorithm that finds all primes up to a limit by marking every multiple of each prime as composite. The numbers never crossed out are the primes. It uses only counting, never division.

What's the time complexity?

O(n log log n) time and O(n) space — far faster than testing each number for primality on its own.

Why start crossing out at p²?

Every multiple of p below p² already has a smaller prime factor and was crossed out earlier. So you can safely begin at p × p.

Is 1 a prime number?

No. A prime has exactly two distinct divisors (1 and itself); 1 has only one, so it's neither prime nor composite.

Where is it used?

Generating prime tables for number theory, competitive programming and crypto pre-computation. For a single huge number, probabilistic tests like Miller–Rabin are used instead.

Finished this one? 0 / 99 Algorithms done

NextMiller–Rabin: Probably Prime Next on the “Number theory, in order” ladder · rung 5 of 6

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Algorithms & DSA