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.

Practice

1. What is the main purpose of the Sieve of Eratosthenes algorithm?

easy

A. To find all prime numbers up to a given limit

B. To sort a list of numbers in ascending order

C. To find the greatest common divisor of two numbers

D. To calculate the factorial of a number

Solution

1. Step 1: Understand the algorithm's goal

   The Sieve of Eratosthenes is designed to identify prime numbers efficiently.

2. Step 2: Recognize the output

   It marks multiples of primes as non-prime, leaving primes unmarked up to the limit.

3. Final Answer:

   To find all prime numbers up to a given limit -> Option A

4. Quick Check:

   Sieve of Eratosthenes = Find primes [OK]

Hint: Sieve marks multiples to find primes fast [OK]

Common Mistakes:

• Confusing it with sorting algorithms
• Thinking it calculates factorials
• Assuming it finds divisors instead of primes

2. Which of the following Python code snippets correctly initializes the sieve list for finding primes up to n?

easy

A. sieve = [False] * n

B. sieve = list(range(n))

C. sieve = [True] * (n+1)

D. sieve = [0] * (n-1)

Solution

1. Step 1: Understand sieve initialization

   The sieve list should mark all numbers as potentially prime initially, so all True.

2. Step 2: Check correct length

   It must include index n, so length is n+1.

3. Final Answer:

   sieve = [True] * (n+1) -> Option C

4. Quick Check:

   Initialize all True for 0 to n [OK]

Hint: Use True for all numbers including n [OK]

Common Mistakes:

• Using False instead of True initially
• Not including n in the list length
• Using range instead of boolean list

3. What will be the output of the following code snippet?

n = 10
sieve = [True] * (n+1)
sieve[0], sieve[1] = False, False
for i in range(2, int(n**0.5)+1):
    if sieve[i]:
        for j in range(i*i, n+1, i):
            sieve[j] = False
primes = [i for i in range(n+1) if sieve[i]]
print(primes)

medium

A. [1, 2, 3, 5, 7]

B. [2, 3, 5, 7]

C. [2, 3, 4, 5, 7]

D. [0, 2, 3, 5, 7]

Solution

1. Step 1: Initialize sieve and mark 0,1 as non-prime

   Indices 0 and 1 are set to False, others True initially.

2. Step 2: Mark multiples of primes as False

   For i=2 and i=3 (since sqrt(10) ~3), multiples 4,6,8,9,10 are marked False.

3. Step 3: Collect primes

   Numbers with True are 2,3,5,7.

4. Final Answer:

   [2, 3, 5, 7] -> Option B

5. Quick Check:

   Primes up to 10 = [2,3,5,7] [OK]

Hint: Remember to exclude 0 and 1 as non-prime [OK]

Common Mistakes:

• Including 1 as prime
• Forgetting to start inner loop at i*i
• Marking wrong multiples

4. Identify the error in this Sieve of Eratosthenes code snippet:

n = 15
sieve = [True] * (n+1)
sieve[0], sieve[1] = False, False
for i in range(2, n):
    if sieve[i]:
        for j in range(i*2, n+1, i):
            sieve[j] = False
primes = [i for i in range(n+1) if sieve[i]]
print(primes)

medium

A. Inner loop should start from i*i, not i*2

B. sieve list length should be n, not n+1

C. sieve[0] and sieve[1] should be True

D. Outer loop should run until n+1, not n

Solution

1. Step 1: Check inner loop start index

   Starting from i*2 marks some multiples multiple times, inefficient.

2. Step 2: Correct start is i*i

   Because smaller multiples are already marked by smaller primes.

3. Final Answer:

   Inner loop should start from i*i, not i*2 -> Option A

4. Quick Check:

   Start inner loop at i*i for efficiency [OK]

Hint: Start marking multiples from i squared [OK]

Common Mistakes:

• Starting inner loop at i*2 wastes time
• Incorrect sieve length causes index errors
• Marking 0 or 1 as prime

5. Using the Sieve of Eratosthenes, how many prime numbers are there between 1 and 30 (inclusive)?

hard

A. 8

B. 11

C. 12

D. 10

Solution

1. Step 1: List primes up to 30 using sieve logic

   Primes are 2,3,5,7,11,13,17,19,23,29.

2. Step 2: Count the primes

   Count is 10 primes between 1 and 30 inclusive.

3. Final Answer:

   10 -> Option D

4. Quick Check:

   Count primes ≤30 = 10 [OK]

Hint: Count primes carefully, exclude 1 and non-primes [OK]

Common Mistakes:

• Including 1 as prime
• Forgetting to include 29
• Miscounting primes between 20 and 30