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.