Sieve of Eratosthenes Find All Primes in DSA Python

Mental Model

We mark multiples of each prime number as not prime, so only primes remain unmarked.

Analogy: Imagine you have a list of numbers like seats in a theater. You start by marking every seat that is a multiple of 2 as taken, then every multiple of 3, and so on, leaving only prime-numbered seats free.

Numbers: 2 3 4 5 6 7 8 9 10
Marks:  _ _ X _ X _ X X  X
_ means unmarked (potential prime), X means marked (not prime)

Dry Run Walkthrough

Input: Find all primes up to 10

Goal: Identify all prime numbers from 2 to 10 using the sieve method

Step 1: Start with list from 2 to 10, all unmarked

2 3 4 5 6 7 8 9 10
_ _ _ _ _ _ _ _  _

Why: We begin assuming all numbers are prime candidates

Step 2: Mark multiples of 2 (except 2) as not prime

2 3 4 5 6 7 8 9 10
_ _ X _ X _ X _  X

Why: Multiples of 2 cannot be prime

Step 3: Move to next unmarked number 3, mark its multiples (except 3)

2 3 4 5 6 7 8 9 10
_ _ X _ X _ X X  X

Why: Multiples of 3 are not prime

Step 4: Next unmarked number is 5, mark multiples (none within range)

2 3 4 5 6 7 8 9 10
_ _ X _ X _ X X  X

Why: No multiples of 5 to mark up to 10

Step 5: Next unmarked number is 7, mark multiples (none within range)

2 3 4 5 6 7 8 9 10
_ _ X _ X _ X X  X

Why: No multiples of 7 to mark up to 10

Result:

Primes are numbers with _ marks: 2 3 5 7

Annotated Code

DSA Python

def sieve_of_eratosthenes(n: int) -> list[int]:
    if n < 2:
        return []
    prime = [True] * (n + 1)  # Assume all numbers are prime initially
    prime[0], prime[1] = False, False  # 0 and 1 are not prime
    p = 2
    while p * p <= n:
        if prime[p]:
            for i in range(p * p, n + 1, p):
                prime[i] = False  # Mark multiples of p as not prime
        p += 1
    return [num for num in range(2, n + 1) if prime[num]]

# Driver code
n = 10
primes = sieve_of_eratosthenes(n)
print("Primes up to", n, ":", " -> ".join(map(str, primes)) + " -> null")

prime = [True] * (n + 1) # Assume all numbers are prime initially

Initialize list marking all numbers as potential primes

prime[0], prime[1] = False, False # 0 and 1 are not prime

Explicitly mark 0 and 1 as not prime

while p * p <= n:

Only need to check primes up to square root of n

if prime[p]:

If current number is still marked prime, proceed to mark multiples

for i in range(p * p, n + 1, p):

Mark all multiples of p starting from p squared as not prime

prime[i] = False # Mark multiples of p as not prime

Mark multiples to exclude them from primes

p += 1

Move to next number to check

return [num for num in range(2, n + 1) if prime[num]]

Collect all numbers still marked prime

Output

Primes up to 10 : 2 -> 3 -> 5 -> 7 -> null

Complexity Analysis

Time: O(n log log n) because we mark multiples of primes efficiently up to n

Space: O(n) because we store a boolean list for all numbers up to n

vs Alternative: Compared to checking each number individually for primality (O(n√n)), sieve is much faster for large n

Edge Cases

n less than 2

Returns empty list since no primes exist below 2

DSA Python

if n < 2:
        return []

n equals 2

Returns list with only 2 as prime

DSA Python

prime[0], prime[1] = False, False  # 0 and 1 are not prime

When to Use This Pattern

When asked to find all primes up to a number efficiently, use the sieve pattern because it marks multiples once and avoids repeated checks.

Common Mistakes

Mistake: Starting to mark multiples from p*2 instead of p*p
Fix: Start marking from p squared because smaller multiples were already marked by smaller primes

Mistake: Not marking 0 and 1 as not prime initially
Fix: Explicitly mark 0 and 1 as False before starting the sieve

Summary

Finds all prime numbers up to a given limit by marking multiples of primes as not prime.

Use when you need a fast way to list primes up to a number.

The key insight is to start marking multiples from the square of each prime to avoid redundant work.