Vibe Engines
ALGORITHMS · 07  /  SIEVE OF ERATOSTHENES

Prime Time.

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

  1. Assume everything's prime. List 2…N. (1 is a special case — neither prime nor composite.)
  2. Find the next survivor. The smallest number not yet crossed out is the next prime, p.
  3. Cross out its multiples. Mark 2p, 3p, 4p… as composite — they all have p as a factor, so none can be prime.
  4. 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.

QUICK CHECK

Did it stick?

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.

RESULT

—

Next → testing one enormous number for primality, where you can't cross out the whole number line. That's Miller–Rabin.

Finished this one? 0 / 7 Algorithms done

More Algorithms

Explore more from Vibe Engines

Handbooks →
Roadmaps →
System Designs →
AI System Designs →
Labs →