## Learning objectives

Now that we have seen that Euclid’s GCD algorithm offers an enormous improvement of efficiency over a trivial approach — even on a fast modern computer — we wonder whether the same will be true for the sieve of Eratosthenes.

Both the sieve of Eratosthenes and a simpler approach for prime finding generate an array of boolean variables to store whether a given integer is prime. Therefore, to prepare ourselves to implement these algorithms, we will need to learn how Go implements arrays.

## Setup

Create a new folder called `arrays`

in your `go/src`

directory, and then create a new file within the `go/src/arrays`

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("Arrays (and slices).") }

## 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

### Introduction to arrays

In Go, arrays have a fixed, constant size. This means that you cannot declare an array of length *n*, and once you declare an array, you are not allowed to change the length of the array. (Don’t worry, we will soon have a workaround for these quirks.)

We can declare arrays in the same way that we declare any other variable, using the `var`

keyword, followed by the name of the array, followed by the type of the array. For example, to declare an array of integers called `list`

of length 6, we can use the following notation:

var list [6]int

Let’s use this idea to declare an array of integers of length 6 and then print the array to the console.

func main() { fmt.Println("Arrays (and slices).") // arrays in Go have a fixed, constant size. var list [6]int // gives 6 default (zero) values fmt.Println(list) }

STOP:Open a command line terminal and navigate into the folder containing your code by using the command`cd go/src/arrays`

. Then, compile your code by executing the command`go build`

. You can then run the code by executing the command`arrays.exe`

on Windows or`./arrays`

on Mac.

As a result of running our code, we should see six zeroes printed to the console because when we declare an array of length n, each element of the array receives the default value for the type of the array, which we know in the case of an `int`

type is zero. If we were to declare an array of strings, then each variable in the array would have value equal to the empty string (`""`

).

Note:In Go, every variable in an array must have the same type.

In Go, the *i*-th value of the array `list`

is denoted `list[i]`

. Go is like many modern languages, and the pseudocode that we showed earlier, in that it uses 0-based indexing. That is, an array having *n* values has indices ranging between 0 and *n* – 1. Let’s use these ideas to set the first value of our array `list`

equal to -8; to do so, we use the notation `list[0] = -8`

as if we were setting any other variable equal to a value.

func main() { fmt.Println("Arrays (and slices).") // arrays in Go have a fixed, constant size. var list [6]int // gives 6 default (zero) values list[0] = -8 fmt.Println(list) }

We can even set a value of the array where the index is given by some arithmetic expression, as shown below.

func main() { fmt.Println("Arrays (and slices).") // arrays in Go have a fixed, constant size. var list [6]int // gives 6 default (zero) values list[0] = -8 i := 3 list[2*i-4] = 17 // 2*i - 4 = 2 fmt.Println(list) }

We can determine the length of a given array by using the built-in function `len()`

. This is helpful in setting the final value of an array `list`

, since we know that the indices of `list`

range between 0 and `len(list)`

– 1. We use this idea below to set the final element of `list`

equal to 43.

func main() { fmt.Println("Arrays (and slices).") // arrays in Go have a fixed, constant size. var list [6]int // gives 6 default (zero) values list[0] = -8 i := 3 list[2*i-4] = 17 // 2*i - 4 = 2 list[len(list)-1] = 43 fmt.Println(list) }

STOP:Compile and run your code. We have set the elements of`list`

at indices 0, 2, and 5, and you should see the output`-8 0 17 0 0 43`

printed to the console.

### Setting an element of an array with index out of bounds

You might wonder what happens if we try to set the value of `list`

for an index that is outside of the range from 0 to `len(list)`

– 1. Whether the index is negative or larger than `len(list)`

– 1, we will obtain a compiler error when attempting to set an element of an array with such an index because the index is **out of bounds**. The following two additional lines show examples of setting elements of an array that would lead to such a compiler error.

func main() { fmt.Println("Arrays (and slices).") // arrays in Go have a fixed, constant size. var list [6]int // gives 6 default (zero) values list[0] = -8 i := 3 list[2*i-4] = 17 // 2*i - 4 = 2 list[len(list)-1] = 43 list[len(list)] = 7 // compiler error! list[-4] = 2 // compiler error! fmt.Println(list) }

Let’s make sure to comment out the two lines in func main() that result in a compiler error so that this error does not occur later on.

func main() { fmt.Println("Arrays (and slices).") // arrays in Go have a fixed, constant size. var list [6]int // gives 6 default (zero) values list[0] = -8 i := 3 list[2*i-4] = 17 // 2*i - 4 = 2 list[len(list)-1] = 43 //list[len(list)] = 7 // compiler error! //list[-4] = 2 // compiler error! fmt.Println(list) }

### When arrays fall short

Let us consider a function `FactorialArray()`

that takes an integer `n`

as input and returns an array `fact`

of length `n+1`

such that `fact[k]`

is equal to `k!`

. Using what we have learned, we might write this function in the following way.

//FactorialArray takes as input an integer n. //It returns the slice of length n+1 whose k-th element is k! func FactorialArray(n int) [n+1]int { if n < 0 { panic("Error: negative input given to FactorialArray().") } var fact [n+1]int fact[0] = 1 for k := 1; k <= n; k++ { fact[k] = fact[k-1] * k } return fact }

Unfortunately, when we compile and run `main.go`

, we obtain a compiler error: `non-constant array bound n+1`

. This error corresponds to the function signature, and is related to our us of `[n+1]int`

as the return type of `FactorialArray()`

. Go does not like this statement, or for that matter the declaration `var fact [n+1]int`

, because of what we stated before: in Go, arrays must have fixed length equal to some constant integer value.

For now, place a multiline comment around `FactorialArray()`

using `/*`

and `*/`

. We will return to it after learning a bit more.

### From arrays to slices

Fortunately, we will have an easy workaround when we want to declare an array whose length is equal to a variable (or an expression involving a variable). Our solution is to a data type called a **slice**.

Much like with declaring an array or any other variable, to declare a slice, we use the keyword `var`

, followed by the name of the slice, followed by the type of the slice. But this time, we will not specify the length of the slice. For example, to declare a slice of integers called `a`

, we can use `var a []int`

. Let’s then print `a`

to the console.

func main() { fmt.Println("Arrays (and slices).") //... var a []int fmt.Println(a) }

When we compile and run this code, we see only `[]`

printed to the console because `a`

currently has no elements and has the special value `nil`

. We need an initial length for our slice. Say that we would like for our slice to have length `n`

, where `n`

is an integer. To do so, we set `a`

using `a = make([]int, n)`

.

func main() { fmt.Println("Arrays (and slices).") //... var a []int n := 4 a = make([]int, n) fmt.Println(a) }

Now when we compile and run this code, we see what we might expect printed to the console: `0 0 0 0`

, corresponding to four default integer values. Furthermore, we can set values of `a`

using the same notation for setting values of an array.

func main() { fmt.Println("Arrays (and slices).") //... var a []int n := 4 a = make([]int, n) a[0] = 42 a[2] = -17 fmt.Println(a) }

Although we wanted to introduce arrays by showing their declaration, Go has a one-line declaration for slices that we will use most of the time. In particular, we can declare a slice `b`

of length, say, `n+2`

, with the single line `b := make([]int, n+2)`

.

func main() { fmt.Println("Arrays (and slices).") //... var a []int n := 4 a = make([]int, n) a[0] = 42 a[2] = -17 fmt.Println(a) b := make([]int, n+2) fmt.Println(b) }

### A function for computing all factorials

We can now use what we have learned about slices to update our implementation of `FactorialArray()`

as shown below. We still refer to this function as `FactorialArray()`

even though it will technically return a slice.

//FactorialArray takes as input an integer n. //It returns the slice of length n+1 whose k-th element is k! func FactorialArray(n int) []int { if n < 0 { panic("Error: negative input given to FactorialArray().") } fact := make([]int, n+1) fact[0] = 1 for k := 1; k <= n; k++ { fact[k] = fact[k-1] * k } return fact }

### Arrays are pass by value, and slices are pass by reference

You might be wondering what here is new. After all, once we declare a slice, we use it in the same way that we use an array.

When we introduced functions in a previous code along, we pointed out that Go uses “pass by value” for input parameters. This means that when we pass a variables such as an integer or string into a function, Go creates a copy of that variable and edits the copy, so that the original variable’s value is preserved.

This behavior is the same for arrays, but not for slices. Consider the following two functions, which change the first element of an input array or slice to 1.

func ChangeFirstElementArray(a [6]int) { a[0] = 1 } func ChangeFirstElementSlice(a []int) { a[0] = 1 }

When we call these functions using the code below, we will see that although `ChangeFirstArray()`

creates a copy of `b`

, `ChangeFirstSlice()`

edits `c`

within the function. As a result, you might like to think about slices as pass by reference, since when we pass a slice into a function, we are able to change the underlying data.

func main() { fmt.Println("Arrays (and slices).") //... var c [5]int // is equal to [0, 0, 0, 0, 0] d := make([]int, 5) // also is equal to [0, 0, 0, 0, 0] ChangeFirstElementArray(c) ChangeFirstElementSlice(d) fmt.Println(c) // prints [0, 0, 0, 0, 0] fmt.Println(d) // prints [1, 0, 0, 0, 0] }

Later in the course, we will discuss more about the distinction between arrays and slices and what is happening when a function takes a slice as a parameter. For now, in practice, we will use slices most of the time throughout this course, and in fact, we will typically use the term “array” to refer to a slice.

### Finding the minimum value of a slice

In the main text, we introduced functions for finding the minimum of two integers and the minimum of three integers. Writing infinitely many functions, one for each possible number of input variables, is not a path we want to take. Instead, we would like to take an arbitrary number of inputs.

One way to take the minimum of an arbitrary number of variables is to assume that these variables are stored in a slice `list`

. After ensuring that the list is not empty, we can declare a variable `m`

to hold our minimum that is equal to the initial element of `list`

and then range over the remaining elements of `list`

, updating `m`

every time that we encounter an element that is smaller than the current value of `m`

.

//MinIntegerArray takes as input a slice of integers. //It returns the minimum value in the array. func MinIntegerArray(list []int) int { if len(list) == 0 { panic("Error: Empty list given as input().") } var m int // default value = 0 // range over list, updating m if we find bigger value for i := 0; i < len(list); i++ { if list[i] < m { m = list[i] } } return m }

STOP:`MinIntegerArray()`

looks correct, but it suffers from a bug. What is it?

Our current implementation of `MinIntegerArray()`

will work for some arrays. However, let us consider what happens if every integers in `list`

is positive, such as for the slice `[3, 2, 1]`

. For this input slice, `MinIntegerArray()`

will declare `m`

, which has a default value of zero, and as the function ranges over `list`

, it will never find an element `list[i]`

that is smaller than `m`

. As a result, `m`

is never updated, and `MinIntegerArray()`

will return 0.

One workaround for this bug is to declare `m`

to be equal to `list[0]`

, as follows. Because we set `m`

initially, we can start our ranging at index 1.

//MinIntegerArray takes as input a slice of integers. //It returns the minimum value in the array. func MinIntegerArray(list []int) int { if len(list) == 0 { panic("Error: Empty list given as input.") } m := list[0] // range over list, updating m if we find bigger value for i := 1; i < len(list); i++ { if list[i] < m { m = list[i] } } return m }

An alternative approach is to instead declare `m`

to be equal to zero, but then in the for loop update `m`

either if we are considering the first element *or* if the current element of `list`

is smaller than `m`

. We can then preserve our ranging over the entire slice, and we get to use the “or” keyword (`||`

) that we learned about in the previous lesson.

//MinIntegerArray takes as input a slice of integers. //It returns the minimum value in the array. func MinIntegerArray(list []int) int { if len(list) == 0 { panic("Error: Empty list given as input.") } var m int // has default value of zero // range over list, updating m if we find bigger value for i := 0; i < len(list); i++ { if i == 0 || list[i] < m { m = list[i] } } return m }

### Shorthand ranging tricks

Go offers two shorthand tricks for working with arrays that we will apply to the second correct implementation of `MinIntegerArray()`

as an example.

The first trick addresses the commonness of ranging over all the indices of an array or slice. Rather than needing the lengthy statement `for i := 0; i < len(list); i++`

, we can instead apply the shorthand `for i := range list`

. We apply this change to `MinIntegerArray()`

below.

//MinIntegerArray takes as input a slice of integers. //It returns the minimum value in the array. func MinIntegerArray(list []int) int { if len(list) == 0 { panic("Error: Empty list given as input.") } var m int // has default value of zero // range over list, updating m if we find bigger value for i := range list { // equivalent to for i:=0; i<len(list); i++ if i == 0 || list[i] < m { m = list[i] } } return m }

The second trick allows us to range over both the indices and the values of an array or slice. If we intend to use `list[i]`

, and especially if we plan to use it more than once, we can use the ranging shorthand `for i, val := range list`

. Here, `val`

is a variable (that we are able to name what we like) holding the current value of `list[i]`

.

//MinIntegerArray takes as input a slice of integers. //It returns the minimum value in the array. func MinIntegerArray(list []int) int { if len(list) == 0 { panic("Error: Empty list given as input.") } var m int // default value = 0 // range over list, updating m if we find bigger value for i, val := range list { if i == 0 || val < m { m = val } } return m }

We may also wish to range over only the values of an array, as exemplified by our first correct implementation of `MinIntegerArray()`

. In this case, because `i`

is not being used, we use an underscore (`_`

) to indicate to Go that we do not intend to declare a variable equal to the current array index.

//MinIntegerArray takes as input a slice of integers. //It returns the minimum value in the slice. func MinIntegerArray(list []int) int { if len(list) == 0 { panic("Error: Empty list given as input.") } m := list[0] // range over list, updating m if we find bigger value for _, val := range list { if val < m { m = val } } return m }

STOP:This last implementation of`MinIntegerArray()`

has a minor inefficiency. What is it?

### Variadic functions

We may also want to find the minimum of an arbitrary collection of input integers without assuming that these integers are contained within an array. A **variadic function** is a function can take an arbitrary number of variables.

In Go, we use the notation `vars`

` ...type`

in a function’s parameters to indicate that we wish to take an arbitrary number of variables having type `type`

. The variables `vars`

will be stored in a slice of type `[]type`

, which we can then access as we like. The following `MinIntegers()`

variadic function takes an arbitrary number of integers, which are stored in a slice `numbers`

. We range over this slice in the same way that we ranged over `list`

in `MinIntegerArray()`

.

//MinIntegers takes as input an arbitrary collection of integers. //It returns the minimum value among the input integers. func MinIntegers(numbers ...int) int { if len(numbers) == 0 { panic("Error: No integers given as input.") } var m int // default value = 0 // range over numbers, updating m if we find bigger value for i, val := range numbers { if i == 0 || val < m { m = val } } return m }

Note how similar `MinIntegers()`

is to `MinIntegerArray()`

; the only difference is the inputs that they take. In programming, any time that we see very similar code arising in our work, a red alert should go off in our brains telling us to use a subroutine. This way, we will only have to write (and debug) half as much code.

In this particular case, because we have already implemented `MinIntegerArray()`

, we can use it as a subroutine in `MinIntegers()`

. We will say much more about subroutines as this course progresses.

//MinIntegers takes as input an arbitrary collection of integers. //It returns the minimum value among the input integers. func MinIntegers(numbers ...int) int { if len(numbers) == 0 { panic("Error: No integers given as input.") } return MinIntegerArray(numbers) }

We are now ready to return to apply what we have learned about arrays and slices to implement and compare the prime finding algorithms that we introduced in the main text. How fast could the sieve of Eratosthenes be? Join us to find out!

## 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:

`FactorialArray()`

`MinIntegerArray()`

`MinIntegers()`