Sieve of Eratosthenes Find All Primes in DSA Go - Build from Scratch

Sieve of Eratosthenes Find All Primes

📖 Scenario: You are helping a teacher prepare a list of prime numbers for a math class. The teacher wants to find all prime numbers up to a certain number n. You will use the Sieve of Eratosthenes method, which is a simple and efficient way to find primes.

🎯 Goal: Build a Go program that uses the Sieve of Eratosthenes algorithm to find and print all prime numbers up to a given number n.

📋 What You'll Learn

Create a boolean slice to represent numbers from 0 to n

Initialize the slice to mark all numbers as potentially prime except 0 and 1

Use a loop to mark multiples of each prime as not prime

Print all numbers that remain marked as prime

💡 Why This Matters

🌍 Real World

Finding prime numbers is useful in cryptography, computer security, and number theory research.

💼 Career

Understanding prime number algorithms helps in roles involving algorithm design, security engineering, and software development.

1

Create the boolean slice for numbers up to n

Create an integer variable called n and set it to 30. Then create a boolean slice called isPrime with length n+1.

DSA Go

n := 30
// Your code here

Hint

Use make([]bool, n+1) to create the boolean slice for numbers from 0 to n.

2

Initialize the slice to mark all numbers as prime except 0 and 1

Use a for loop with variable i from 2 to n inclusive to set isPrime[i] to true.

DSA Go

package main

import "fmt"

func main() {
    n := 30
    isPrime := make([]bool, n+1)
    // Your code here
}

Hint

Start from 2 because 0 and 1 are not prime numbers.

3

Mark multiples of each prime as not prime

Use a for loop with variable p from 2 to int(float64(n).Sqrt()) (use p * p <= n as condition). Inside it, check if isPrime[p] is true. If yes, use another for loop with variable multiple starting from p * p to n incrementing by p to set isPrime[multiple] to false.

DSA Go

package main

import "fmt"

func main() {
    n := 30
    isPrime := make([]bool, n+1)
    for i := 2; i <= n; i++ {
        isPrime[i] = true
    }
    // Your code here
}

Hint

Start marking multiples from p * p because smaller multiples were already marked by smaller primes.

4

Print all prime numbers up to n

Use a for loop with variable i from 2 to n inclusive. Inside the loop, if isPrime[i] is true, print i followed by a space. After the loop, print a newline.

DSA Go

package main

import "fmt"

func main() {
    n := 30
    isPrime := make([]bool, n+1)
    for i := 2; i <= n; i++ {
        isPrime[i] = true
    }

    for p := 2; p*p <= n; p++ {
        if isPrime[p] {
            for multiple := p * p; multiple <= n; multiple += p {
                isPrime[multiple] = false
            }
        }
    }

    // Your code here
}

Hint

Print all numbers marked as prime separated by spaces, then print a newline.

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