Sieve of Eratosthenes Find All Primes in DSA Go - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to create a boolean slice to mark primes up to n.

DSA Go

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

Drag options to blanks, or click blank then click option'

A2*n

Bn

Cn-1

Dn+1

Attempts:

3 left

💡 Hint

Common Mistakes

Using size n misses the last number n.

Using size n-1 causes index out of range errors.

We need a slice of size n+1 to include index n for marking primes.

2fill in blank

medium

Complete the code to initialize all numbers as prime (true) except 0 and 1.

DSA Go

for i := 2; i <= [1]; i++ {
    primes[i] = true
}

Drag options to blanks, or click blank then click option'

An

Bn-1

Cn+1

Dn/2

Attempts:

3 left

💡 Hint

Common Mistakes

Looping only to n-1 misses the number n.

Starting from 0 or 1 incorrectly marks them as prime.

We mark all numbers from 2 up to n as true initially.

3fill in blank

hard

Fix the error in the inner loop to mark multiples as not prime.

DSA Go

for j := i * i; j <= n; j += [1] {
    primes[j] = false
}

Drag options to blanks, or click blank then click option'

Ai+1

Bi

C2

Dj

Attempts:

3 left

💡 Hint

Common Mistakes

Using i+1 skips some multiples.

Using 2 marks wrong multiples.

We increment by i to mark all multiples of i as not prime.

4fill in blank

hard

Fill both blanks to complete the outer loop and print primes.

DSA Go

for i := 2; i <= [1]; i++ {
    if primes[i] == [2] {
        fmt.Print(i, " ")
    }
}

Drag options to blanks, or click blank then click option'

An

Btrue

Cfalse

Di

Attempts:

3 left

💡 Hint

Common Mistakes

Checking for false instead of true.

Looping only to n-1 misses last prime.

Loop up to n and print numbers marked true as primes.

5fill in blank

hard

Fill all three blanks to complete the Sieve of Eratosthenes function.

DSA Go

func sieve(n int) {
    primes := make([]bool, [1]+1)
    for i := 2; i <= n; i++ {
        primes[i] = [2]
    }
    for i := 2; i*i <= n; i++ {
        if primes[i] {
            for j := i * i; j <= n; j += [3] {
                primes[j] = false
            }
        }
    }
    for i := 2; i <= n; i++ {
        if primes[i] {
            fmt.Print(i, " ")
        }
    }
}

Drag options to blanks, or click blank then click option'

An

Btrue

Ci

Dfalse

Attempts:

3 left

💡 Hint

Common Mistakes

Wrong slice size causes index errors.

Marking primes false initially causes no output.

Incrementing inner loop by wrong value misses multiples.

Create slice size n+1, mark true initially, increment by i to mark multiples.

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