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

Concept Flow - Sieve of Eratosthenes Find All Primes

Create list of numbers 2 to n

↓

Start with p = 2 (smallest prime)

↓

Mark multiples of p as not prime

↓

Find next number > p not marked

↓

If next p <= sqrt(n), repeat marking

↓

Collect all numbers not marked as primes

Start with a list of numbers, mark multiples of each prime as not prime, then collect remaining primes.

Execution Sample

DSA Go

n := 10
primes := sieve(n)
fmt.Println(primes)

Find all prime numbers up to 10 using the sieve method.

Execution Table

Step	Operation	Current p	Marked Multiples	List State (index: value)	Visual State
1	Initialize list	-	-	2:true 3:true 4:true 5:true 6:true 7:true 8:true 9:true 10:true	2 3 4 5 6 7 8 9 10 all true
2	Start with p=2	2	-	Same as above	p=2, start marking multiples
3	Mark multiples of 2	2	4,6,8,10	2:true 3:true 4:false 5:true 6:false 7:true 8:false 9:true 10:false	Multiples of 2 marked false
4	Find next p > 2	3	-	Same as above	p=3 next prime candidate
5	Mark multiples of 3	3	6,9	2:true 3:true 4:false 5:true 6:false 7:true 8:false 9:false 10:false	Multiples of 3 marked false
6	Find next p > 3	5	-	Same as above	p=5 next prime candidate
7	Mark multiples of 5	5	10	2:true 3:true 4:false 5:true 6:false 7:true 8:false 9:false 10:false	10 already false, no change
8	Find next p > 5	7	-	Same as above	p=7 next prime candidate
9	Mark multiples of 7	7	-	Same as above	No multiples <=10 to mark
10	Next p > 7 is 8 (false), skip to 9 (false), skip to 10 (false)	-	-	Same as above	No more primes <= sqrt(10)
11	Collect primes	-	-	2:true 3:true 5:true 7:true	Primes are 2,3,5,7
12	End	-	-	-	Sieve complete

💡 p exceeded sqrt(n), sieve finished

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 7	Final
p	-	2	3	5	7
List (index: prime?)	All true	4,6,8,10 false	6,9 false	10 false	4,6,8,9,10 false
Primes collected	Empty	Empty	Empty	Empty	[2,3,5,7]

Key Moments - 3 Insights

Why do we start marking multiples from p*p, not from 2*p?

Because smaller multiples of p were already marked by smaller primes. For example, 2*3=6 was marked when p=2. This avoids redundant work (see Step 3 and Step 5 in execution_table).

Why do we stop when p exceeds sqrt(n)?

Because any composite number n must have a factor less than or equal to sqrt(n). Beyond that, all multiples are already marked (see Step 10 in execution_table).

Why do some numbers remain true after marking multiples?

Those numbers are primes because they were never marked as multiples of smaller primes (see final list in Step 11).

Visual Quiz - 3 Questions

Look at the execution_table at Step 3, which numbers are marked false as multiples of 2?

A 4, 6, 8, 10

B 3, 5, 7, 9

C 2, 4, 6, 8

D 5, 7, 9, 10

💡 Hint

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

At which step does p become 5 in the execution_table?

A Step 8

B Step 4

C Step 6

D Step 10

💡 Hint

Look at the 'Current p' column to find when p=5.

If we increased n to 20, how would the 'List State' after marking multiples of 2 change compared to Step 3?

A All numbers would be marked false

B More numbers like 12, 14, 16, 18, 20 would be marked false

C No change, only 4,6,8,10 marked false

D Only prime numbers would be marked false

💡 Hint

Multiples of 2 up to n are marked false; increasing n adds more multiples.

Concept Snapshot

Sieve of Eratosthenes:
- Create list from 2 to n
- Start with p=2
- Mark multiples of p as not prime
- Move to next unmarked number > p
- Stop when p > sqrt(n)
- Remaining unmarked numbers are primes

Full Transcript

The Sieve of Eratosthenes finds all primes up to n by creating a list of numbers from 2 to n. Starting with p=2, it marks all multiples of p as not prime. Then it finds the next number greater than p that is still marked prime and repeats marking its multiples. This continues until p exceeds the square root of n. Finally, all numbers still marked prime are collected as the prime numbers. The process avoids redundant marking by starting from p squared and stops early because any composite number must have a factor less than or equal to sqrt(n).

Practice

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

easy

A. To sort a list of numbers in ascending order

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

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 a limit.

3. Final Answer:

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

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 Go code snippets correctly initializes a boolean slice for the sieve up to n?

easy

A. primes := make([]bool, n-1)

B. primes := make([]int, n)

C. primes := []bool{n}

D. primes := make([]bool, n+1)

Solution

1. Step 1: Identify correct slice type and size

   We need a boolean slice of size n+1 to include index n.

2. Step 2: Check Go syntax for slice creation

   make([]bool, n+1) correctly creates a boolean slice of length n+1.

3. Final Answer:

   primes := make([]bool, n+1) -> Option D

4. Quick Check:

   Boolean slice with length n+1 = primes := make([]bool, n+1) [OK]

Hint: Use make([]bool, n+1) for sieve array [OK]

Common Mistakes:

• Using int slice instead of bool
• Incorrect slice length causing index errors
• Wrong slice initialization syntax

3. What will be the output slice after running the sieve for n = 10 if true means prime and false means not prime?

func sieve(n int) []bool {
    primes := make([]bool, n+1)
    for i := 2; i <= n; i++ {
        primes[i] = true
    }
    for i := 2; i*i <= n; i++ {
        if primes[i] {
            for j := i * i; j <= n; j += i {
                primes[j] = false
            }
        }
    }
    return primes
}

fmt.Println(sieve(10))

medium

A. [false false true true false true false true false false false]

B. [false false true true false true false true false true false]

C. [false false true true false true false true false false true]

D. [false false true true true true false true false false false]

Solution

1. Step 1: Initialize primes slice for n=10

   Indices 0 and 1 are false; 2 to 10 are initially true.

2. Step 2: Mark multiples of primes as false

   Multiples of 2: 4,6,8,10 set false; multiples of 3: 9 set false.

3. Final Answer:

   [false false true true false true false true false false false] -> Option A

4. Quick Check:

   Primes at 2,3,5,7 true; multiples false [OK]

Hint: Mark multiples starting from i*i as false [OK]

Common Mistakes:

• Marking primes as false by mistake
• Starting inner loop from i instead of i*i
• Incorrect slice indexing

4. Identify the error in this Go code implementing the sieve:

func sieve(n int) []bool {
    primes := make([]bool, n)
    for i := 2; i <= n; i++ {
        primes[i] = true
    }
    for i := 2; i*i <= n; i++ {
        if primes[i] {
            for j := i * i; j <= n; j += i {
                primes[j] = false
            }
        }
    }
    return primes
}

medium

A. Inner loop increments by 1 instead of i

B. Loop starts from 2 instead of 0

C. Slice length is n, but indices go up to n causing out-of-range error

D. Boolean slice should be initialized with false values

Solution

1. Step 1: Check slice size vs index usage

   Slice is length n, but code accesses primes[n], which is out of range.

2. Step 2: Understand Go slice indexing

   Valid indices are 0 to n-1, so primes[n] causes runtime panic.

3. Final Answer:

   Slice length is n, but indices go up to n causing out-of-range error -> Option C

4. Quick Check:

   Slice size mismatch causes index error [OK]

Hint: Slice length must be n+1 for index n [OK]

Common Mistakes:

• Ignoring slice length vs index range
• Starting loops incorrectly
• Misunderstanding slice initialization defaults

5. Using the Sieve of Eratosthenes, how many prime numbers are there up to n = 30?

Consider the standard sieve implementation where indices 0 and 1 are not prime.

medium

A. 10

B. 11

C. 12

D. 13

Solution

1. Step 1: List primes up to 30

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

2. Step 2: Count the primes

   Counting gives 10 primes.

3. Final Answer:

   10 -> Option A

4. Quick Check:

   Count primes ≤ 30 = 10 [OK]

Hint: Count primes manually or use sieve output [OK]

Common Mistakes:

• Including non-primes like 9 or 15
• Forgetting to exclude 1 and 0
• Miscounting primes near 30