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()`

and `SieveOfEratosthenes()`

(along with necessary subroutines) from the main text.

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

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.

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()`

and use what we have learned about slices in the previous code along. In the updated `TrivialPrimeFinder()`

function below, we use a two-line declaration of the `primeBooleans`

slice, but we could also use the single-line declaration `primeBooleans := make([]bool, n+1)`

.

//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()`

as well. To do so, we will need to call the `Sqrt()`

function from the `"math"`

package. A first attempt at this function is below.

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()`

produces a compiler error because `math.Sqrt()`

takes a `float64`

as input. To fix this issue, we will cast `p`

to be a `float64`

; we also will need to cast `k`

when comparing it against the resulting square root.

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()`

, let’s now call `TrivialPrimeFinder()`

from `func main()`

and ensure that everything is working properly.

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[3]`

,`primeBooleans[5]`

, and`primeBooleans[7]`

should be`true`

to correspond to the primality of 2, 3, 5, and 7 (see figure below).

### Implementing the sieve of Eratosthenes

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

as well as its subroutine `CrossOffMultiples()`

.

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()`

.

Like `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.

//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`

, every value of this slice will be initialized with the default value of `false`

. This default behavior is different to our desired initialization for the sieve of Eratosthenes, which is for every value other than `primeBooleans[0]`

and `primeBooleans[1]`

to be initialized to `true`

. As a result, we first need a for loop setting all other values of `primeBooleans`

to `true`

.

//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`

between 2 and √*n*. Each time through the loop, we ask “Is `p`

prime?” And if this is the case (i.e., if `primeBooleans[p]`

is `true`

), then we update our `primeBooleans`

array by setting all indices of `primeBooleans`

that are multiples of `p`

equal to `false`

, a task that we pass to a `CrossOffMultiples()`

subroutine. Note below that we need to cast `p`

and `n`

to type `float64`

as we did in `TrivialPrimeFinder()`

.

//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()`

is now complete, and we can turn to implementing `CrossOffMultiples()`

. This function takes a slice `primeBooleans`

of boolean variables as input, along with an integer `p`

. It returns the updated slice after setting `primeBooleans[k]`

equal to `false`

for every index `k`

that is larger than `p`

and a multiple of `p`

.

//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`

are easy to find. We can initialize `k`

equal to `2*p`

, and then add `p`

to `k`

each time as the postcondition of a for loop whose condition is `k <= n`

. We can write our function as follows.

//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`

, then we will unfortunately obtain a compiler error telling us that `n`

is undefined. When we declare `primeBooleans`

within `SieveOfEratosthenes()`

, we use an input parameter `n`

and construct primeBooleans to have length `n+1`

. However, this parameter’s scope is confined to `SieveOfEratosthenes()`

, and `CrossOffMultiples()`

cannot see it. Fortunately, because we know that the length of `primeBooleans`

is 1 larger than `n`

, we can infer that `n`

is equal to the length of `primeBooleans`

minus 1. This brings us to a final implementation of `CrossOffMultiples()`

.

//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()`

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()`

(see our`func main()`

below).

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`

— we just need to add all integers `p`

to this list such that `primeBooleans[p]`

is `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()`

that would call `SieveOfEratosthenes()`

as a subroutine and then produce this list by using a function `append()`

that takes an array of integers `primeList`

and an integer `p`

and adds `p`

to the end of `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()`

, 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()`

as follows, in which we declare our array of primes `primeList`

to have length 0 and then append to it every time we encounter a prime.

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()`

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`

in `ListPrimes()`

.

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()`

within `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`

.

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`

(which we set equal to 1,000,000) by updating `func main()`

as well as the import statements for `main.go`

as follows.

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`

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`

corresponding to every multiple of 2, without needing to call `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()`

`TrivialPrimeFinder()`

`CrossOffMultiples()`

`SieveOfEratosthenes()`

`ListPrimes()`