Sieve of Eratosthenes Find All Primes in DSA Python - Execution Trace

Concept Flow - Sieve of Eratosthenes Find All Primes

Start with list of numbers 2 to n

↓

Mark all numbers as prime initially

↓

Set current = 2 (first prime)

↓

Mark multiples of current as not prime

↓

Find next number > current still marked prime

↓

If next prime <= sqrt(n), repeat marking multiples

↓

Else, stop and collect all primes

↓

Return list of primes

Start with all numbers marked prime, then repeatedly mark multiples of each prime as not prime until done.

Execution Sample

DSA Python

def sieve(n):
    primes = [True]*(n+1)
    primes[0] = primes[1] = False
    p = 2
    while p*p <= n:
        if primes[p]:
            for i in range(p*p, n+1, p):
                primes[i] = False
        p += 1
    return [x for x in range(2, n+1) if primes[x]]

This code finds all prime numbers up to n using the sieve method.

Execution Table

Step	Operation	Current Prime (p)	Multiples Marked	Primes List Snapshot
1	Initialize primes list	-	-	[False, False, True, True, True, True, True, True, True, True, True]
2	Set p=2, check p*p <= 10	2	-	[False, False, True, True, True, True, True, True, True, True, True]
3	Mark multiples of 2 as not prime	2	4,6,8,10	[False, False, True, True, False, True, False, True, False, True, False]
4	Increment p to 3, check p*p <= 10	3	-	[False, False, True, True, False, True, False, True, False, True, False]
5	Mark multiples of 3 as not prime	3	9	[False, False, True, True, False, True, False, True, False, False, False]
6	Increment p to 4, check p*p <= 10	4	-	[False, False, True, True, False, True, False, True, False, False, False]
7	4 is not prime, skip marking	4	-	[False, False, True, True, False, True, False, True, False, False, False]
8	Increment p to 5, check p*p <= 10	5	-	[False, False, True, True, False, True, False, True, False, False, False]
9	Check p=5, p*p=25 >10, stop marking	5	-	[False, False, True, True, False, True, False, True, False, False, False]
10	Collect primes from list	-	-	[2, 3, 5, 7]

💡 p*p > n (5*5=25 > 10), so sieve marking stops.

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 7	Final
p	2	2	3	4	5
primes	[False, False, True, True, True, True, True, True, True, True, True]	[False, False, True, True, False, True, False, True, False, True, False]	[False, False, True, True, False, True, False, True, False, False, False]	[False, False, True, True, False, True, False, True, False, False, False]	[False, False, True, True, False, True, False, True, False, False, False]

Key Moments - 3 Insights

Why do we start marking multiples from p*p instead of 2*p?

Because all smaller multiples of p (like 2*p, 3*p, ...) were already marked by smaller primes. See execution_table step 3 where marking starts at 4 (2*2).

Why do we stop when p*p > n?

Because any composite number less than or equal to n must have a prime factor less than or equal to sqrt(n). So no need to check beyond p where p*p > n. See execution_table step 9.

Why do we mark primes[p] = False for multiples but not p itself?

Because p is prime at that step, only its multiples are composite. The code checks primes[p] before marking multiples, ensuring p stays True. See execution_table steps 3 and 5.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, which numbers are marked as not prime?

A 3, 5, 7, 9

B 2, 3, 5, 7

C 4, 6, 8, 10

D 1, 2, 3, 4

💡 Hint

Check the 'Multiples Marked' column at step 3 in execution_table.

At which step does the algorithm stop marking multiples?

A Step 9

B Step 7

C Step 5

D Step 10

💡 Hint

Look at the exit_note and step 9 in execution_table where p*p > n.

If n was 25, what would be the last prime p used for marking multiples?

A 6

B 5

C 7

D 4

💡 Hint

Recall the stopping condition p*p > n; for n=25, p=5 because 5*5=25.

Concept Snapshot

Sieve of Eratosthenes finds primes up to n.
Start with all numbers marked prime.
For each prime p starting at 2, mark multiples p*p, p*p+p, ... as not prime.
Stop when p*p > n.
Return all numbers still marked prime.

Full Transcript

The Sieve of Eratosthenes algorithm starts by assuming all numbers from 2 to n are prime. It then iteratively picks the smallest number still marked prime, called p, and marks all multiples of p starting from p squared as not prime. This process repeats with the next prime number until p squared is greater than n. Finally, the algorithm collects all numbers still marked prime and returns them as the list of primes up to n.

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