Sieve of Eratosthenes Explained: Easy Step-by-Step Guide

Imagine you need every prime number from 1 up to 100—or up to 100,000. Checking every single number one by one with long division would take forever!

Over 2,200 years ago, a Greek scholar named Eratosthenes (the chief librarian at the Great Library of Alexandria) invented a brilliant shortcut that finds all the primes at once—without doing a single division problem.

Think of it like shaking sand through a kitchen sifter (or sieve): the composite numbers fall through the holes, and only the prime numbers stay behind.

---

1. How the Sieve Works: Cross Out the Multiples

Instead of trying to prove which numbers are prime, the sieve flips the task around: start with a number grid and cross out everything you know is NOT prime.

Step-by-Step Example: Finding Every Prime up to 100

1. Cross out 1 right away: 1 has only one factor, so it is neither prime nor composite. Write down 2 through 100.
2. Start at 2 (circle it!):
   • 2 is your first prime.
   • Cross out every bigger multiple of 2 (4, 6, 8, 10, ..., 100). Just like that, half the grid is gone!
3. Move to the next open number, 3 (circle it!):
   • Cross out multiples of 3 (6, 9, 12, 15, ..., 99).
   • Notice 6 and 12 were already crossed out by 2—the very first fresh number to cross out is 3 × 3 = 9.
4. Move to 5 (circle it!):
   • Cross out multiples of 5 (10, 15, 20, 25, ..., 95).
   • Notice the first fresh number not already crossed off is 5 × 5 = 25.
5. Move to 7 (circle it!):
   • Cross out multiples of 7 (14, 21, 28, ..., 98).
   • The first fresh number here is 7 × 7 = 49 (plus 77 and 91!).
6. Time to Stop at 11!
   • The next open number is 11, and 11 × 11 = 121 is bigger than 100.
   • You can stop immediately! Every uncrossed number left on your page is 100% guaranteed to be prime.

Here are all 25 primes left standing between 1 and 100: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

---

2. Two Smart Speed Shortcuts

When you run this trick on a computer—or by hand on a bigger chart—two easy rules save huge amounts of effort:

Shortcut 1: Always Start Crossing at p × p (p²)

When you start crossing out multiples of 7, you don’t need to waste time checking 7 × 2 = 14, 7 × 3 = 21, or 7 × 5 = 35. Why? Every smaller multiple k × p (where k < p) was already crossed out by that smaller number k:

• 2 × 7 = 14 was crossed out during step 2
• 3 × 7 = 21 was crossed out during step 3
• 4 × 7 = 28 was crossed out during step 2
• 5 × 7 = 35 was crossed out during step 5
• 6 × 7 = 42 was crossed out during step 2
• The first fresh multiple is always 7 × 7 = 49!

Shortcut 2: Stop Checking Once p > √N

As soon as your prime reaches the square root of your chart’s top limit (√N), p × p jumps past the end of your list. Everything still uncrossed after √N cannot possibly have a smaller factor—otherwise that smaller factor would have already crossed it off!

To find every prime up to 1,000,000, you only need to run the crossing loop for primes up to √1,000,000 = 1,000 (just 168 primes!).

---

3. Why Computers Love the Sieve

Dividing big numbers takes lots of CPU steps. Counting forward (p², p² + p, p² + 2p, …) uses simple addition, which computers do almost instantly.

How many total marks does the sieve make up to N?

• Multiples of 2 cross off N / 2 boxes
• Multiples of 3 cross off N / 3 boxes
• Multiples of 5 cross off N / 5 boxes, and so on.

Because the fractions 1/2 + 1/3 + 1/5 + 1/7 + ... grow astonishingly slowly (a pattern math writers label O(N log log N)), even checking 10 million numbers only crosses each box roughly 3 times on average! It runs nearly as fast as simply reading through a list once.

---

4. Simple Ways Coders Make It Even Faster

While Eratosthenes’ idea is 2,200 years old, modern programmers tweak how it uses computer memory so it scales to hundreds of millions of numbers:

Trick 1: Skip All Even Numbers & Pack Flags Tightly

After 2, no even number can ever be prime. Skipping even numbers instantly cuts your list size in half. Packing 8 yes/no checkmarks into a single byte (instead of one full byte per number) cuts memory 16× smaller—shrinking a 100 MB list down to roughly 6.25 MB!

Trick 2: Split Big Lists into Small Chunks (Segmented Sieve)

Modern processors have a tiny, super-fast built-in workspace (CPU cache) right next to the chip. A single giant list up to 1 billion overflows that workspace and slows down waiting for main RAM.

A chunked (segmented) sieve fixes this neatly:

1. First find all primes up to √N in one tiny list.
2. Walk through [1, N] in small slices (for example, 32 KB at a time) that fit comfortably inside the processor’s fastest memory.
3. Cross off multiples inside each slice one piece at a time! That speeds up huge searches by 8× to 12×.

---

5. Clean Code Examples

Python (Odd-Only Sieve)

def sieve_of_eratosthenes(limit: int) -> list[int]:
    """Returns all prime numbers up to 'limit' while skipping evens."""
    if limit < 2:
        return []

    # Track odd numbers only: slot i stands for (2*i + 1)
    size = (limit - 1) // 2
    is_prime = [True] * (size + 1)

    limit_sqrt = int(limit ** 0.5)
    for i in range(1, (limit_sqrt - 1) // 2 + 1):
        if is_prime[i]:
            p = 2 * i + 1
            # Start crossing out at p * p
            start = (p * p - 1) // 2
            is_prime[start::p] = [False] * len(is_prime[start::p])

    return [2] + [2 * i + 1 for i in range(1, size + 1) if is_prime[i]]

print(sieve_of_eratosthenes(100))
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

JavaScript (Fast Browser Array Sieve)

export function sievePrimes(limit) {
  if (limit < 2) return [];

  const isComposite = new Uint8Array(limit + 1);
  const primes = [2];
  const sqrtLimit = Math.floor(Math.sqrt(limit));

  for (let p = 3; p <= sqrtLimit; p += 2) {
    if (!isComposite[p]) {
      primes.push(p);
      const step = 2 * p; // skip even multiples
      for (let multiple = p * p; multiple <= limit; multiple += step) {
        isComposite[multiple] = 1;
      }
    }
  }

  // Collect remaining uncrossed odd numbers above sqrtLimit
  const start = sqrtLimit % 2 === 0 ? sqrtLimit + 1 : sqrtLimit + 2;
  for (let p = Math.max(3, start); p <= limit; p += 2) {
    if (!isComposite[p]) primes.push(p);
  }

  return primes;
}

---

6. When Should You Use the Sieve?

What You Want to Do	Best Tool to Use	Why
Check one giant number (like 15 digits)	Fast 7-base prime test	Takes less than a millisecond without building a list
List all primes from 1 to 1,000,000	Sieve of Eratosthenes	Finds hundreds of thousands of primes in milliseconds
List primes in a high window (e.g. 1,000,000 to 1,001,000)	Chunked (Segmented) Sieve	Doesn’t waste memory on numbers below the start
Learn primes in class	1–100 Sieve Grid	Easy visual way to watch composite numbers disappear

---

Quick Questions & Answers

Why do we start crossing out at p × p instead of 2 × p?

Because every smaller multiple (like 2p, 3p, 5p) has a smaller prime factor, so it was already crossed out in an earlier step! For example, 7 × 5 = 35 was crossed out when we handled 5.

What is the Sieve of Atkin?

Discovered in 2003, the Sieve of Atkin uses a trickier set of formulas that looks faster on paper for truly astronomical limits. In real-world software up to several billion, however, a well-tuned chunked Sieve of Eratosthenes is usually simpler and just as fast—or faster!

---

Interactive Tools & Calculators

• Watch numbers cross out step by step: Sieve of Eratosthenes Visualizer
• Find primes between any two limits: Primes Between Calculator
• Count how many primes exist up to any number: Prime Counting Calculator
• Check a single number right now: Prime Number Calculator