Sieve of Eratosthenes Find All Primes in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Sieve for n=10

What is the output list of primes after running the Sieve of Eratosthenes for n=10?

DSA Go

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

fmt.Println(sieve(10))

A [2, 3, 5, 7]

B [2, 3, 4, 5, 7]

C [1, 2, 3, 5, 7]

D [2, 3, 5, 7, 9]

💡 Hint

Remember primes are numbers greater than 1 with no divisors other than 1 and themselves.

The sieve marks multiples of each prime starting from its square as not prime. For n=10, primes are 2, 3, 5, and 7 only.

❓ Predict Output

intermediate

Count of primes up to 20

How many prime numbers are found by the sieve for n=20?

DSA Go

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

fmt.Println(sieveCount(20))

A 10

B 9

C 7

D 8

💡 Hint

List primes up to 20: 2,3,5,7,11,13,17,19

There are exactly 8 primes less than or equal to 20.

🔧 Debug

advanced

Identify the error in sieve implementation

What error does this code produce when running sieve(10)?

DSA Go

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

A runtime error: index out of range

B compilation error: missing return statement

C returns empty list

D runs correctly and returns primes

💡 Hint

Check the size of the boolean slice and the indices used.

The slice primes has length n, but code accesses primes[n], which is out of range causing runtime panic.

🧠 Conceptual

advanced

Why start marking multiples from p*p?

In the Sieve of Eratosthenes, why do we start marking multiples of a prime p from p*p instead of 2*p?

A Because p*p is the smallest prime number

B Because smaller multiples of p are already marked by smaller primes

C Because 2*p is not a multiple of p

D Because starting from 2*p causes index out of range

💡 Hint

Think about when multiples get marked in earlier steps.

Multiples less than p*p have already been marked by smaller primes, so starting at p*p avoids redundant work.

🚀 Application

expert

Find sum of primes up to 50 using sieve

What is the sum of all prime numbers up to 50 found by the Sieve of Eratosthenes?

DSA Go

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

fmt.Println(sieveSum(50))

A 350

B 311

C 328

D 300

💡 Hint

Sum primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47

The sum of primes up to 50 is 328.

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