Sieve of Eratosthenes: Explained Intuitively

Build an intuitive model of the Sieve of Eratosthenes so you can generate primes quickly, know why $p^2$ and $\sqrt{N}$ matter, estimate cost, and avoid common implementation bugs and scaling traps.

Primes feel like they should require a lot of testing. The sieve flips that instinct. You do not try to prove each number is prime. You assume everything is prime, then repeatedly remove numbers that cannot be. What is left is not guessed, it is forced. The surprising part is how little work that takes once you notice you are crossing out whole families of numbers at a time, and how early you can stop.

Find primes by not testing them

Think of the numbers from 2 to N as a crowd where only the composites wear a visible badge. The sieve does not inspect each person. It posts simple rules like anyone divisible by 2 is out, then divisible by 3, then 5, and so on. Each rule eliminates many numbers in one sweep.

Use this visualization to watch those sweeps layer on top of each other and see what survives.

After a few passes, the pattern changes. New primes are not discovered by tests, they are the next uncrossed number you stumble into. The sieve keeps your attention on structure, not on one number at a time.

Rule of thumb: If a number is still uncrossed when you reach it, treat it as prime and let it eliminate its multiples for you.

The two stopping tricks that make it fast

The Sieve of Eratosthenes works because it refuses to do redundant work. Two ideas carry most of the savings.

Start crossing at $p^2$

When you find a prime p, it is tempting to cross out 2p, 3p, 4p right away. You do not need to. Every multiple kp with k < p has a smaller factor than p, so it would have been crossed out when you processed that smaller factor.

That means the first multiple of p you need to newly eliminate is p*p.

Stop at $\sqrt{N}$

If a composite m ≤ N exists, it has some factor a ≤ √m ≤ √N. So once you have processed primes up to √N, every composite up to N has already been hit by its smallest prime factor. Everything still uncrossed above that point is automatically prime.

Run a small simulation and watch how 2p and 3p get eliminated before p ever gets a turn, and why the crossing naturally begins at p*p.

This is also why sieve code often has a loop condition like p*p <= N. It is not a trick. It is the stopping condition stated in the same language your program speaks.

Why the sieve is correct

Every composite number has a smallest prime factor. That one sentence is the whole engine.

If m is composite, it can be written as m = ab with a and b bigger than 1. Keep factoring a until you reach a prime. That prime divides m, and among all primes that divide m, one is smallest. Call it p.

Now connect that to the sieve. When the sieve reaches p, it crosses out every multiple of p starting at p*p. Since m is a multiple of p, it will be crossed out unless m < p*p. But m < p*p would imply m = p*q with q < p, which contradicts p being the smallest prime factor.

The same idea explains the √N stop. If m ≤ N is composite and both factors were greater than √N, their product would exceed N. So at least one factor is ≤ √N, and the sieve will have processed it.

Open the proof sketch step by step if you want to see where each contradiction comes from.

Time and space tradeoffs you actually feel

The sieve is fast because it pays a small cost per crossed out number, not a full trial division for each candidate.

A basic sieve maintains a boolean array of length about N+1. Each prime p crosses out about N/p numbers. Summed over primes, that work behaves like $O(N\log\log N)$, which grows surprisingly slowly. Memory is the more practical limiter. A naive boolean per number costs about N bytes in many languages, unless you bit-pack it.

Trial division is the opposite trade. Almost no memory, but lots of repeated divisibility checks.

Use this comparison to see how the choices change as N jumps from 10^6 to 10^8, including the effect of cache friendliness.

Practical limit: When N gets large, segmented sieving often wins not because it is fewer operations, but because it keeps the working set small enough to stay cache friendly.

Implementation failure modes that bite

The math is clean. The code is where things go sideways.

• Off-by-one on inclusive N means you silently drop N itself or allocate the wrong array size.
• Forgetting that 0 and 1 are not prime makes your output look plausible until someone checks edge cases.
• Overflow in p*p happens when p is near the integer limit, which can break the p*p <= N stop condition.
• Odd-only sieves are easy to get wrong because index i no longer means number i.

The safest way to debug is to keep a firm mapping between array indices and the numbers they represent, especially after compression. Use this interactive map to toggle common choices like inclusive endpoints and odd-only storage and see how the indexing shifts.

A solid mental habit is to write the mapping as a tiny comment near the array. For odd-only, for example, you want something like index i represents number 2*i + 1, and then every crossing formula is derived from that, not improvised.

Variants that change the mental model

The classic sieve assumes you can hold 2..N in memory and sweep across it. Two common variants keep the same correctness idea but reorganize the work.

Segmented sieve

Instead of one giant array, you sieve a block like [L, R] at a time. You still need primes up to √N first, but then you reuse them to cross out multiples inside each block. The key mental shift is that crossing out is now relative to the block start, so you compute the first multiple of p inside [L, R] and mark from there.

Wheel factorization

A wheel does not change what is composite. It changes what you bother to represent. If you skip all even numbers, you already applied the p=2 rule in your data model. If you also skip multiples of 3 and 5, your candidates are numbers coprime to 30. You trade more complex stepping for fewer marks.

See the two flows side by side to feel how the same idea can live in different data layouts.

Where sieving fits in your toolkit

Use a sieve when you need many primes up to a limit, or repeated queries like how many primes are ≤ N, prime gaps, factoring lots of medium-sized numbers, or generating primes for cryptography experiments at toy scales.

Do not use it when N is huge and you only need to test one number for primality. A probabilistic primality test or deterministic checks for your range can be far cheaper than allocating memory up to N. Also, if you need primes in an interval far away like around 10^12, a segmented sieve over that window makes sense, while a full sieve up to 10^12 does not.

Your next step is concrete. Pick one target problem. Generate all primes up to 10^7 with a basic sieve, then redo it with odd-only storage, then redo it with segmentation. You will feel exactly where time goes and why the textbook ideas matter.