Implementing Prime Finding Algorithms in Go

We are now ready to return to our second main narrative in this chapter, finding prime numbers. In the preceding lesson, we saw that Euclid’s algorithm offers a substantial and surprising improvement over a trivial approach. How will the sieve of Eratosthenes fare against a simpler prime finding approach?

Below, we reproduce our pseudocode for

TrivialPrimeFinder()
TrivialPrimeFinder() and
SieveOfEratosthenes()
SieveOfEratosthenes() (along with necessary subroutines) from the main text.

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
TrivialPrimeFinder(n)
primeBooleans ← array of n+1 false boolean variables
for every integer p from 2 to n
if IsPrime(p) is true
primeBooleans[p]true
return primeBooleans
IsPrime(p)
for every integer k between 2 and √p
if k is a divisor of p
return false
return true
TrivialPrimeFinder(n) primeBooleans ← array of n+1 false boolean variables for every integer p from 2 to n if IsPrime(p) is true primeBooleans[p] ← true return primeBooleans IsPrime(p) for every integer k between 2 and √p if k is a divisor of p return false return true
TrivialPrimeFinder(n)
    primeBooleans ← array of n+1 false boolean variables
    for every integer p from 2 to n
        if IsPrime(p) is true
            primeBooleans[p] ← true
    return primeBooleans

IsPrime(p)
    for every integer k between 2 and √p
        if k is a divisor of p
            return false
    return true
Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
SieveOfEratosthenes(n)
primeBooleans ← array of n+1 true boolean variables
primeBooleans[0]false
primeBooleans[1]false
for every integer p between 2 and √n
if primeBooleans[p] = true
primeBooleans ← CrossOffMultiples(primeBooleans, p)
return primeBooleans
CrossOffMultiples(primeBooleans, p)
n ← length(primeBooleans) - 1
for every multiple k of p (from 2p to n)
primeBooleans[k]false
return primeBooleans
SieveOfEratosthenes(n) primeBooleans ← array of n+1 true boolean variables primeBooleans[0] ← false primeBooleans[1] ← false for every integer p between 2 and √n if primeBooleans[p] = true primeBooleans ← CrossOffMultiples(primeBooleans, p) return primeBooleans CrossOffMultiples(primeBooleans, p) n ← length(primeBooleans) - 1 for every multiple k of p (from 2p to n) primeBooleans[k] ← false return primeBooleans
SieveOfEratosthenes(n)
    primeBooleans ← array of n+1 true boolean variables
    primeBooleans[0] ← false
    primeBooleans[1] ← false
    for every integer p between 2 and √n
        if primeBooleans[p] = true
            primeBooleans ← CrossOffMultiples(primeBooleans, p)
    return primeBooleans

CrossOffMultiples(primeBooleans, p)
    n ← length(primeBooleans) - 1
    for every multiple k of p (from 2p to n)
        primeBooleans[k] ← false
    return primeBooleans

In this lesson, we will implement these two algorithms and time them.

Setup

Create a new folder called primes in your go/src directory, and then create a new file within the go/src/primes folder called main.go, which we will edit in this lesson.

In main.go, add the following starter code.

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
package main
import (
"fmt"
)
func main() {
fmt.Println("Finding primes.")
}
package main import ( "fmt" ) func main() { fmt.Println("Finding primes.") }
package main

import (
    "fmt"
)

func main() {
    fmt.Println("Finding primes.")
}

Code along video

Beneath the video, we provide a detailed summary of the topics and code covered in the code along.

At the bottom of this page, you will have the opportunity to validate your work via auto-graded assessments that evaluate the functions covered in the code along.

Although we strongly suggest completing the code along on your own, you can find completed code from the code along in our course code repository.

Code along summary

The trivial prime finding algorithm

We are now ready to return to

TrivialPrimeFinder()
TrivialPrimeFinder() and use what we have learned about slices in the previous code along. In the updated
TrivialPrimeFinder()
TrivialPrimeFinder() function below, we use a two-line declaration of the
primeBooleans
primeBooleans slice, but we could also use the single-line declaration
primeBooleans := make([]bool, n+1)
primeBooleans := make([]bool, n+1).

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
//TrivialPrimeFinder takes an integer n and produces a boolean array of length n+1
//where primeBooleans[p] is true if p is prime (and false otherwise)
func TrivialPrimeFinder(n int) []bool {
var primeBooleans []bool // type is "slice of booleans", which default to false
primeBooleans = make([]bool, n+1)
// in general, you'll just use primeBooleans := make([]bool, n+1)
for p := 2; p <= n; p++ {
if IsPrime(p) == true {
primeBooleans[p] = true
}
}
return primeBooleans
}
//TrivialPrimeFinder takes an integer n and produces a boolean array of length n+1 //where primeBooleans[p] is true if p is prime (and false otherwise) func TrivialPrimeFinder(n int) []bool { var primeBooleans []bool // type is "slice of booleans", which default to false primeBooleans = make([]bool, n+1) // in general, you'll just use primeBooleans := make([]bool, n+1) for p := 2; p <= n; p++ { if IsPrime(p) == true { primeBooleans[p] = true } } return primeBooleans }
//TrivialPrimeFinder takes an integer n and produces a boolean array of length n+1
//where primeBooleans[p] is true if p is prime (and false otherwise)
func TrivialPrimeFinder(n int) []bool {
    var primeBooleans []bool // type is "slice of booleans", which default to false
    primeBooleans = make([]bool, n+1)

    // in general, you'll just use primeBooleans := make([]bool, n+1)

    for p := 2; p <= n; p++ {
        if IsPrime(p) == true {
            primeBooleans[p] = true
        }
    }

    return primeBooleans
}

We will need to implement

IsPrime()
IsPrime() as well. To do so, we will need to call the
Sqrt()
Sqrt() function from the
"math"
"math" package. A first attempt at this function is below.

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
func IsPrime(p int) bool {
for k := 2; k <= math.Sqrt(p); k++ {
if p%k == 0 {
return false
}
}
return true
}
func IsPrime(p int) bool { for k := 2; k <= math.Sqrt(p); k++ { if p%k == 0 { return false } } return true }
func IsPrime(p int) bool {
    for k := 2; k <= math.Sqrt(p); k++ {
        if p%k == 0 {
            return false
        }
    }
    return true
}

Unfortunately, this version of

IsPrime()
IsPrime() produces a compiler error because
math.Sqrt()
math.Sqrt() takes a
float64
float64 as input. To fix this issue, we will cast
p
p to be a
float64
float64; we also will need to cast
k
k when comparing it against the resulting square root.

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
func IsPrime(p int) bool {
for k := 2; float64(k) <= math.Sqrt(float64(p)); k++ {
if p%k == 0 {
return false
}
}
return true
}
func IsPrime(p int) bool { for k := 2; float64(k) <= math.Sqrt(float64(p)); k++ { if p%k == 0 { return false } } return true }
func IsPrime(p int) bool {
    for k := 2; float64(k) <= math.Sqrt(float64(p)); k++ {
        if p%k == 0 {
            return false
        }
    }
    return true
}

Now that we have implemented

IsPrime()
IsPrime(), let’s now call
TrivialPrimeFinder()
TrivialPrimeFinder() from
func main()
func main() and ensure that everything is working properly.

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
func main() {
fmt.Println("Primes and arrays.")
primeBooleans := TrivialPrimeFinder(10)
fmt.Println(primeBooleans)
}
func main() { fmt.Println("Primes and arrays.") primeBooleans := TrivialPrimeFinder(10) fmt.Println(primeBooleans) }
func main() {
    fmt.Println("Primes and arrays.")

    primeBooleans := TrivialPrimeFinder(10)
    fmt.Println(primeBooleans)
}
STOP: Compile and run main.go. You should see false false true true false true false true false false false printed to the console. This is correct because
primeBooleans[2]
primeBooleans[2],
primeBooleans[3]
primeBooleans[3],
primeBooleans[5]
primeBooleans[5], and
primeBooleans[7]
primeBooleans[7] should be
true
true to correspond to the primality of 2, 3, 5, and 7 (see figure below).
i
i
012345678910
primeBooleans[i]
primeBooleans[i]
false
false
false
false
true
true
true
true
false
false
true
true
false
false
true
true
false
false
false
false
false
false
Figure: A table showing the values of
primeBooleans[i]
primeBooleans[i] for an array of length 11.

Implementing the sieve of Eratosthenes

We are now ready to implement the sieve of Eratosthenes. Below, we reproduce the pseudocode for

SieveOfEratosthenes()
SieveOfEratosthenes() as well as its subroutine
CrossOffMultiples()
CrossOffMultiples().

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
SieveOfEratosthenes(n)
primeBooleans ← array of n+1 true boolean variables
primeBooleans[0]false
primeBooleans[1]false
for every integer p between 2 and √n
if primeBooleans[p] = true
primeBooleans ← CrossOffMultiples(primeBooleans, p)
return primeBooleans
CrossOffMultiples(primeBooleans, p)
n ← length(primeBooleans) - 1
for every multiple k of p (from 2p to n)
primeBooleans[k]false
return primeBooleans
SieveOfEratosthenes(n) primeBooleans ← array of n+1 true boolean variables primeBooleans[0] ← false primeBooleans[1] ← false for every integer p between 2 and √n if primeBooleans[p] = true primeBooleans ← CrossOffMultiples(primeBooleans, p) return primeBooleans CrossOffMultiples(primeBooleans, p) n ← length(primeBooleans) - 1 for every multiple k of p (from 2p to n) primeBooleans[k] ← false return primeBooleans
SieveOfEratosthenes(n)
    primeBooleans ← array of n+1 true boolean variables
    primeBooleans[0] ← false
    primeBooleans[1] ← false
    for every integer p between 2 and √n
        if primeBooleans[p] = true
            primeBooleans ← CrossOffMultiples(primeBooleans, p)
    return primeBooleans

CrossOffMultiples(primeBooleans, p)
    n ← length(primeBooleans) - 1
    for every multiple k of p (from 2p to n)
        primeBooleans[k] ← false
    return primeBooleans

You may wish to recall how the sieve of Eratosthenes works, as illustrated in the figure below. It first assumes that every integer is prime. Then, over a sequence of steps, it identifies the smallest number in the table that is not composite, and then it “crosses off” all of that number’s factors larger than itself (i.e., sets them to be composite), which is the work of CrossOffMultiples().

Figure: An animation illustrating the sieve of Eratosthenes.

Like

TrivialPrimeFinder()
TrivialPrimeFinder(), we will need to declare primeBooleans as a slice of boolean variables. We know that this array will have length n+1, and so we can declare it to have this length. Let’s start writing our function below.

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
//SieveOfEratosthenes takes an integer n and returns a slice of n+1
//booleans primeBooleans where primeBooleans[p] is true if p is prime
//and false otherwise.
//It implements the sieve of Eratosthenes approach for finding primes.
func SieveOfEratosthenes(n int) []bool {
primeBooleans := make([]bool, n+1)
// the meat of our function will go here
return primeBooleans
}
//SieveOfEratosthenes takes an integer n and returns a slice of n+1 //booleans primeBooleans where primeBooleans[p] is true if p is prime //and false otherwise. //It implements the sieve of Eratosthenes approach for finding primes. func SieveOfEratosthenes(n int) []bool { primeBooleans := make([]bool, n+1) // the meat of our function will go here return primeBooleans }
//SieveOfEratosthenes takes an integer n and returns a slice of n+1
//booleans primeBooleans where primeBooleans[p] is true if p is prime
//and false otherwise.
//It implements the sieve of Eratosthenes approach for finding primes.
func SieveOfEratosthenes(n int) []bool {
    primeBooleans := make([]bool, n+1)

    // the meat of our function will go here

    return primeBooleans
}

When we declare

primeBooleans
primeBooleans, every value of this slice will be initialized with the default value of
false
false. This default behavior is different to our desired initialization for the sieve of Eratosthenes, which is for every value other than
primeBooleans[0]
primeBooleans[0] and
primeBooleans[1]
primeBooleans[1] to be initialized to
true
true. As a result, we first need a for loop setting all other values of
primeBooleans
primeBooleans to
true
true.

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
//SieveOfEratosthenes takes an integer n and returns a slice of n+1
//booleans primeBooleans where primeBooleans[p] is true if p is prime
//and false otherwise.
//It implements the sieve of Eratosthenes approach for finding primes.
func SieveOfEratosthenes(n int) []bool {
primeBooleans := make([]bool, n+1)
// set everything to prime other than primeBooleans[0] and primeBooleans[1]
for k := 2; k <= n; k++ {
primeBooleans[k] = true
}
return primeBooleans
}
//SieveOfEratosthenes takes an integer n and returns a slice of n+1 //booleans primeBooleans where primeBooleans[p] is true if p is prime //and false otherwise. //It implements the sieve of Eratosthenes approach for finding primes. func SieveOfEratosthenes(n int) []bool { primeBooleans := make([]bool, n+1) // set everything to prime other than primeBooleans[0] and primeBooleans[1] for k := 2; k <= n; k++ { primeBooleans[k] = true } return primeBooleans }
//SieveOfEratosthenes takes an integer n and returns a slice of n+1
//booleans primeBooleans where primeBooleans[p] is true if p is prime
//and false otherwise.
//It implements the sieve of Eratosthenes approach for finding primes.
func SieveOfEratosthenes(n int) []bool {
    primeBooleans := make([]bool, n+1)

    // set everything to prime other than primeBooleans[0] and primeBooleans[1]
    for k := 2; k <= n; k++ {
        primeBooleans[k] = true
    }

    return primeBooleans
}

Next we are ready to implement the engine of the sieve. We use a for loop to range over all

p
p between 2 and √n. Each time through the loop, we ask “Is
p
p prime?” And if this is the case (i.e., if
primeBooleans[p]
primeBooleans[p] is
true
true), then we update our
primeBooleans
primeBooleans array by setting all indices of
primeBooleans
primeBooleans that are multiples of
p
p equal to
false
false, a task that we pass to a
CrossOffMultiples()
CrossOffMultiples() subroutine. Note below that we need to cast
p
p and
n
n to type
float64
float64 as we did in
TrivialPrimeFinder()
TrivialPrimeFinder().

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
//SieveOfEratosthenes takes an integer n and returns a slice of n+1
//booleans primeBooleans where primeBooleans[p] is true if p is prime
//and false otherwise.
//It implements the sieve of Eratosthenes approach for finding primes.
func SieveOfEratosthenes(n int) []bool {
primeBooleans := make([]bool, n+1)
// set everything to prime other than primeBooleans[0] and primeBooleans[1]
for k := 2; k <= n; k++ {
primeBooleans[k] = true
}
// now, range over primeBooleans, and cross off multiples of first prime we see, iterating this process.
for p := 2; float64(p) <= math.Sqrt(float64(n)); p++ {
if primeBooleans[p] == true {
primeBooleans = CrossOffMultiples(primeBooleans, p)
}
}
return primeBooleans
}
//SieveOfEratosthenes takes an integer n and returns a slice of n+1 //booleans primeBooleans where primeBooleans[p] is true if p is prime //and false otherwise. //It implements the sieve of Eratosthenes approach for finding primes. func SieveOfEratosthenes(n int) []bool { primeBooleans := make([]bool, n+1) // set everything to prime other than primeBooleans[0] and primeBooleans[1] for k := 2; k <= n; k++ { primeBooleans[k] = true } // now, range over primeBooleans, and cross off multiples of first prime we see, iterating this process. for p := 2; float64(p) <= math.Sqrt(float64(n)); p++ { if primeBooleans[p] == true { primeBooleans = CrossOffMultiples(primeBooleans, p) } } return primeBooleans }
//SieveOfEratosthenes takes an integer n and returns a slice of n+1
//booleans primeBooleans where primeBooleans[p] is true if p is prime
//and false otherwise.
//It implements the sieve of Eratosthenes approach for finding primes.
func SieveOfEratosthenes(n int) []bool {
    primeBooleans := make([]bool, n+1)

    // set everything to prime other than primeBooleans[0] and primeBooleans[1]
    for k := 2; k <= n; k++ {
        primeBooleans[k] = true
    }

    // now, range over primeBooleans, and cross off multiples of first prime we see, iterating this process.
    for p := 2; float64(p) <= math.Sqrt(float64(n)); p++ {
        if primeBooleans[p] == true {
            primeBooleans = CrossOffMultiples(primeBooleans, p)
        }
    }

    return primeBooleans
}

SieveOfEratosthenes()
SieveOfEratosthenes() is now complete, and we can turn to implementing
CrossOffMultiples()
CrossOffMultiples(). This function takes a slice
primeBooleans
primeBooleans of boolean variables as input, along with an integer
p
p. It returns the updated slice after setting
primeBooleans[k]
primeBooleans[k] equal to
false
false for every index
k
k that is larger than
p
p and a multiple of
p
p.

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
//CrossOffMultiples takes a boolean slice and an integer p. It crosses off
//multiples of p, meaning turning these multiples to false in the slice.
//It returns the slice obtained as a result.
func CrossOffMultiples(primeBooleans []bool, p int) []bool {
// let's fill in
}
//CrossOffMultiples takes a boolean slice and an integer p. It crosses off //multiples of p, meaning turning these multiples to false in the slice. //It returns the slice obtained as a result. func CrossOffMultiples(primeBooleans []bool, p int) []bool { // let's fill in }
//CrossOffMultiples takes a boolean slice and an integer p.  It crosses off
//multiples of p, meaning turning these multiples to false in the slice.
//It returns the slice obtained as a result.
func CrossOffMultiples(primeBooleans []bool, p int) []bool {
    // let's fill in
}

These indices

k
k are easy to find. We can initialize
k
k equal to
2*p
2*p, and then add
p
p to
k
k each time as the postcondition of a for loop whose condition is
k <= n
k <= n. We can write our function as follows.

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
//CrossOffMultiples takes a boolean slice and an integer p. It crosses off
//multiples of p, meaning turning these multiples to false in the slice.
//It returns the slice obtained as a result.
func CrossOffMultiples(primeBooleans []bool, p int) []bool {
for k := 2*p; k <= n; k += p {
primeBooleans[k] = false // k is composite
}
return primeBooleans
}
//CrossOffMultiples takes a boolean slice and an integer p. It crosses off //multiples of p, meaning turning these multiples to false in the slice. //It returns the slice obtained as a result. func CrossOffMultiples(primeBooleans []bool, p int) []bool { for k := 2*p; k <= n; k += p { primeBooleans[k] = false // k is composite } return primeBooleans }
//CrossOffMultiples takes a boolean slice and an integer p.  It crosses off
//multiples of p, meaning turning these multiples to false in the slice.
//It returns the slice obtained as a result.
func CrossOffMultiples(primeBooleans []bool, p int) []bool {
    for k := 2*p; k <= n; k += p {
        primeBooleans[k] = false // k is composite
    }
    return primeBooleans
}
STOP: This function has a problem; can you find it?

If we compile

main.go
main.go, then we will unfortunately obtain a compiler error telling us that
n
n is undefined. When we declare
primeBooleans
primeBooleans within
SieveOfEratosthenes()
SieveOfEratosthenes(), we use an input parameter
n
n and construct primeBooleans to have length
n+1
n+1. However, this parameter’s scope is confined to
SieveOfEratosthenes()
SieveOfEratosthenes(), and
CrossOffMultiples()
CrossOffMultiples() cannot see it. Fortunately, because we know that the length of
primeBooleans
primeBooleans is 1 larger than
n
n, we can infer that
n
n is equal to the length of
primeBooleans
primeBooleans minus 1. This brings us to a final implementation of
CrossOffMultiples()
CrossOffMultiples().

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
//CrossOffMultiples takes a boolean slice and an integer p. It crosses off
//multiples of p, meaning turning these multiples to false in the slice.
//It returns the slice obtained as a result.
func CrossOffMultiples(primeBooleans []bool, p int) []bool {
n := len(primeBooleans) - 1
for k := 2*p; k <= n; k += p {
primeBooleans[k] = false // k is composite
}
return primeBooleans
}
//CrossOffMultiples takes a boolean slice and an integer p. It crosses off //multiples of p, meaning turning these multiples to false in the slice. //It returns the slice obtained as a result. func CrossOffMultiples(primeBooleans []bool, p int) []bool { n := len(primeBooleans) - 1 for k := 2*p; k <= n; k += p { primeBooleans[k] = false // k is composite } return primeBooleans }
//CrossOffMultiples takes a boolean slice and an integer p.  It crosses off
//multiples of p, meaning turning these multiples to false in the slice.
//It returns the slice obtained as a result.
func CrossOffMultiples(primeBooleans []bool, p int) []bool {
    n := len(primeBooleans) - 1
    for k := 2*p; k <= n; k += p {
        primeBooleans[k] = false // k is composite
    }
    return primeBooleans
}
STOP: Make sure that
SieveOfEratosthenes()
SieveOfEratosthenes() is working by calling it on an input of 10 and printing out the resulting slice and ensuring that you get the same result that we did when calling
TrivialPrimeFinder()
TrivialPrimeFinder() (see our
func main()
func main() below).
Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
func main() {
fmt.Println("Primes and arrays.")
primeBooleans := SieveOfEratosthenes(10)
fmt.Println(primeBooleans)
}
func main() { fmt.Println("Primes and arrays.") primeBooleans := SieveOfEratosthenes(10) fmt.Println(primeBooleans) }
func main() {
    fmt.Println("Primes and arrays.")

    primeBooleans := SieveOfEratosthenes(10)
    fmt.Println(primeBooleans)
}

Listing out primes exemplifies appending to slices in Go

Although we have implemented algorithms to find all prime numbers, there is nevertheless something unsatisfying about what we have done because we are assigning boolean variables to all integers, but we are not producing a list of primes. This task can be completed easily once we have computed

primeBooleans
primeBooleans — we just need to add all integers
p
p to this list such that
primeBooleans[p]
primeBooleans[p] is
true
true.

In fact, we mentioned this task in the main text when introducing prime finding algorithms. At that time, we discussed a pseudocode function

ListPrimes()
ListPrimes() that would call
SieveOfEratosthenes()
SieveOfEratosthenes() as a subroutine and then produce this list by using a function
append()
append() that takes an array of integers
primeList
primeList and an integer
p
p and adds
p
p to the end of
primeList
primeList.

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
ListPrimes(n)
primeList ← array of integers of length 0
primeBooleans ← SieveOfEratosthenes(n)
for every integer p from 0 to n+1
if primeBooleans[p] = true
primeList ← append(primeList, p)
return primeList
ListPrimes(n) primeList ← array of integers of length 0 primeBooleans ← SieveOfEratosthenes(n) for every integer p from 0 to n+1 if primeBooleans[p] = true primeList ← append(primeList, p) return primeList
ListPrimes(n)
    primeList ← array of integers of length 0
    primeBooleans ← SieveOfEratosthenes(n)
    for every integer p from 0 to n+1
        if primeBooleans[p] = true
            primeList ← append(primeList, p)
    return primeList

Go has exactly such a function

append()
append(), which takes a slice as well as a variable (of the type corresponding to the slice) and adds this variable to the end of the slice, returning the resulting slice. We use this function to implement
ListPrimes()
ListPrimes() as follows, in which we declare our array of primes
primeList
primeList to have length 0 and then append to it every time we encounter a prime.

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
func ListPrimes(n int) []int {
primeList := make([]int, 0)
primeBooleans := SieveOfEratosthenes(n) // remember: primeBooleans will have length n+1
//range over primeBooleans, and append p to primeList if p is prime
for p := 0; p < n+1; p++ {
if primeBooleans[p] == true {
primeList = append(primeList, p)
}
}
return primeList
}
func ListPrimes(n int) []int { primeList := make([]int, 0) primeBooleans := SieveOfEratosthenes(n) // remember: primeBooleans will have length n+1 //range over primeBooleans, and append p to primeList if p is prime for p := 0; p < n+1; p++ { if primeBooleans[p] == true { primeList = append(primeList, p) } } return primeList }
func ListPrimes(n int) []int {
    primeList := make([]int, 0)
    primeBooleans := SieveOfEratosthenes(n) // remember: primeBooleans will have length n+1
    
    //range over primeBooleans, and append p to primeList if p is prime
    for p := 0; p < n+1; p++ {
        if primeBooleans[p] == true {
            primeList = append(primeList, p)
        }
    }

    return primeList
}
Note:
ListPrimes()
ListPrimes() illustrates a general theme of programming with slices, which is that if we don’t know in advance how long a slice needs to be, we can initiate the slice to have length 0 and append to it each time we need to add an element to the list.

We will also apply the shorthand that we learned in the previous lesson to range over element of

primeBooleans
primeBooleans in
ListPrimes()
ListPrimes().

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
func ListPrimes(n int) []int {
primeList := make([]int, 0)
primeBooleans := SieveOfEratosthenes(n) // remember: primeBooleans will have length n+1
//range over primeBooleans, and append p to primeList if p is prime
for p := range primeBooleans {
if primeBooleans[p] == true {
primeList = append(primeList, p)
}
}
return primeList
}
func ListPrimes(n int) []int { primeList := make([]int, 0) primeBooleans := SieveOfEratosthenes(n) // remember: primeBooleans will have length n+1 //range over primeBooleans, and append p to primeList if p is prime for p := range primeBooleans { if primeBooleans[p] == true { primeList = append(primeList, p) } } return primeList }
func ListPrimes(n int) []int {
    primeList := make([]int, 0)
    primeBooleans := SieveOfEratosthenes(n) // remember: primeBooleans will have length n+1
    
    //range over primeBooleans, and append p to primeList if p is prime
    for p := range primeBooleans {
        if primeBooleans[p] == true {
            primeList = append(primeList, p)
        }
    }

    return primeList
}

We can now call

ListPrimes()
ListPrimes() within
func main()
func main() to ensure that it works. The following code should print 2 3 5 7 11 to the console when we compile and run main.go.

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
func main() {
fmt.Println("Primes and arrays.")
primeList := ListPrimes(11)
fmt.Println(primeList)
}
func main() { fmt.Println("Primes and arrays.") primeList := ListPrimes(11) fmt.Println(primeList) }
func main() {
    fmt.Println("Primes and arrays.")

    primeList := ListPrimes(11)
    fmt.Println(primeList)
}

Timing the two prime finding algorithms

Now that we have implemented two prime finding algorithms, we should time them as we did when comparing our GCD algorithms in the preceding lesson. We can time the two functions for a given

n
n (which we set equal to 1,000,000) by updating
func main()
func main() as well as the import statements for main.go as follows.

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
package main
import (
"log"
"time"
"math"
)
func main() {
n := 1000000
start := time.Now()
TrivialPrimeFinder(n)
elapsed := time.Since(start)
log.Printf("TrivialPrimeFinder took %s", elapsed)
start2 := time.Now()
SieveOfEratosthenes(n)
elapsed2 := time.Since(start2)
log.Printf("SieveOfEratosthenes took %s", elapsed2)
}
package main import ( "log" "time" "math" ) func main() { n := 1000000 start := time.Now() TrivialPrimeFinder(n) elapsed := time.Since(start) log.Printf("TrivialPrimeFinder took %s", elapsed) start2 := time.Now() SieveOfEratosthenes(n) elapsed2 := time.Since(start2) log.Printf("SieveOfEratosthenes took %s", elapsed2) }
package main

import (
    "log"
    "time"
    "math"
)

func main() {
    n := 1000000

    start := time.Now()
    TrivialPrimeFinder(n)
    elapsed := time.Since(start)
    log.Printf("TrivialPrimeFinder took %s", elapsed)

    start2 := time.Now()
    SieveOfEratosthenes(n)
    elapsed2 := time.Since(start2)
    log.Printf("SieveOfEratosthenes took %s", elapsed2)
}
STOP: Compile and run this code, either on your computer or by using the window below. Try changing
n
n to have smaller and larger values. What do you find?

Once again, we see an astonishing speedup over a trivial algorithm provided by a simple mathematical insight. In this case, why that insight even provides an insight is quite subtle. Rather than checking that each integer is prime, we save a great deal of time by crossing off the multiples of known primes. In one subroutine call, for example, we cross off half the integers up to

n
n corresponding to every multiple of 2, without needing to call
IsPrime()
IsPrime() on all these integers.

After giving you the chance to check your work, we will return once more to the main text and an epilogue, where we reflect on the efficiency of the sieve of Eratosthenes and discuss a modern application that relies on fast algorithms for finding primes.

Check your work from the code along

We provide autograders in the window below (or via a direct link) allowing you to check your work for the following functions:

  • IsPrime()
    IsPrime()
  • TrivialPrimeFinder()
    TrivialPrimeFinder()
  • CrossOffMultiples()
    CrossOffMultiples()
  • SieveOfEratosthenes()
    SieveOfEratosthenes()
  • ListPrimes()
    ListPrimes()

close

Love P4❤️? Join us and help share our journey!

Page Contents