What You are Going to Learn

This lesson is a little different. We want to show you some tips, that you can use to make programming just a little bit simpler.

Why Now?

We could have introduced these before now, at the point where we introduced each concept. But we choose not to so that we could keep the initial lessons as simple as possible.

This collection of tips will make writing programs just a little bit easier. Most of the time they save you a little bit of typing. But some of them help Go tell you when you have made a mistake.

All of the tips, are very common. Most Go programmer use these tips everyday. So if you can use or remember them it will make reading another programmers program easier.

Information

None of the things we are about to show you are required. You don’t have to use them if you don’t want to. You can still write any program without using and of these tricks.

Variables

The first tip is about variables. Remember that the variables use three patterns for a variable. The first pattern is to declare a variable and its type. This pattern looks like this:

var variable-name variable-type

The second pattern sets a value to the variable. This pattern looks like:

variable-name = new-value

The last pattern tells you how to use a variable. You just use the variable’s name when ever you want to use the value of the variable in your program.

This tip combines the first two patterns into a single step. It allows you to both declare and assign an initial value to a variable in one step. This saves you a little bit of typing by asking Go to work out the correct type for you.

The pattern is:

var variable-name = initial-value

Go will work out the type of the variable for you, based on the initial value that you assign to the variable. You don’t have to supply the type yourself.

Let’s look at some real examples of this pattern.

var myName = "Bob"
var firstPrimeNumber = 2
var averageDistanceToTheMoonInLightSeconds =  1.282
var areWeThereYet = false
Fig-1. Some examples of assigned the value to a variable when it is declared.

So Go thinks that myName is a string type because you assigned the string "Bob" to it. Go knows that it is a string, because of the inverted commas around Bob.

firstPrimeNumber is a whole number, so Go uses the integer, int type for this.

averageDistanceToTheMoonInLightSeconds is a decimal fraction, so Go uses its largest floating point type to hold the number, a float64.

The last example, areWeThereYet is the answer to a question, or the condition, used in an if statement or a for loop. We have set the initial value to false. Remember that in Go a condition can only have the answer true or false. Go represents this using a boolean, or bool type. This type can only hold the special values true or false.

Remember that you can only use this tip if you know the initial value of a variable when you declare it. Most of the time you don’t know the value. For example if the user has to type in the value when the program runs. In these cases you still have to specify the type of the variable when you declare it. Then you can assign a new value to it later in your program.

Constants

The second tip is about a new concept called a constant. A constant, is the opposite of a variable. The value of a variable can change. It changes when you assign a new value to it. The value of a constant can never change. The value of a constant must also be set when it it declared.

Why is This Useful?

We use constants for three things.

The first use for constants is to represent things outside of your program that we know will never change like, mathematical constants, such as the value of pi, Π. Or physical constants, such as the speed of light which is 299792458 meters per second.

The second use for constants is to represent something within your program that you do not want to change. For example think of a game were the score a player needs to win is 11 points. As a programmer you do not want the value of the winning score to change. If it did the rules of the game would be different and you might have a bug in your program. To avoid this you would use a constant to hold the winning score.

The last use of a constant is to prevent your mistakes! If you declare a value as a constant, the Go will tell you before you run your program, if you have accidentally tried to change the value of the constant. Think of the winning score example again. How much help would it be if Go spotted that you had accidentally changed the winning score to 10?

Constant Patterns

The simplest pattern to declare a constant looks like this:

const constant-name = constant-value

For example, you would use this to create a constant for the value of pi, like this:

const pi = 3.14159

You can use constants for strings and whole, integer, numbers as well. Like this:

const maxScreenWidth = 1024
const welcomeMessage = "Hello, good evening and welcome"

When you want to use a constant you use the constant name in the same way that you use a variable-name when you want the value of a variable. As an example this is how you would calculate the perimeter of a circle.

const pi = 3.14159
var radius float64
radius = 5.432 // for example
var perimeter float64
perimeter = 2.0 * pi * radius
Fig-2. Using an constant in a program

You might have noticed that when we declare a constant in this way, you don’t need to tell Go which type the constant is. Go will automatically work out the type for you, in the same way that it can do with variables.

If you try to assign a new value to a constant, Go will prevent you from doing this. For example if you had this simple program:

1package main
2
3func main() {
4    const n = 1
5    n = n + 1
6}
Fig-3. Trying to change the value of a constant.

Go will tell you that there is an error on line 5. The error will be cannot assign to n. You cannot assign a new value to, n because it is a constant.

Lists of Variables

The third tip helps you reduce the number of times you need to type var when you declare a variable.

If you want to declare more than one variable at the same time you can group these together inside brackets. If you do this you only need to use the var keyword once, outside the brackets.

Let’s show you an example.

var (
    myName = "Alice"
    yourName string
    myAge int
)
Fig-4. Grouping variables together when you declare them.

this has exactly the same meaning as:

var myName = "Alice"
var yourName string
var myAge int

except its just less to type. As you can see from the example you can use the first tip, to set the value of variable when you declare it. We have done this for the myName variable in the example.

You can also use this tip with constants. If you have a list of constants to define you can do it like this:

const pi = 3.14159
const maxScreenWidth = 1024
const welcomeMessage = "Hello, good evening and welcome"
Fig-5. Grouping constants together when you define them.

You might have already spotted that we have used this tip many times before, but with the import keyword when we needed to import multiple packages at a time.

Here is an example from the Sieve of Eratosthenes from the (repetition lesson)https://gophercoders.com/lessons/ks2/lower/further-repetition/

import (
    "fmt"
    "math"
    "github.com/gophercoders/simpleio"
)
Fig-6. Grouping packages in a import statement.

Less Typing for Arithmetic

This tip is easiest to explain with an example first.

Imagine we had an integer variable, myAge that we wanted to make one bigger, because today is my birthday. This is how you would do it.

myAge = myAge + 1

Easy. Except there are two other, easier ways!

The first way is the more general way, so we’ll show you that first.

You can rewrite the example like this:

myAge += 1

Which is exactly the same as the longer myAge = myAge + 1. Both ways add 1 to the value of the variable myAge.

But you aren’t restricted to just adding, you can use subtraction, multiplication and division as well. And you don’t have to add one, you can use any number.

These are all valid

var myAge = 12
myAge += 4 // myAge is now 16 because it is 12 + 4
myAge /= 2 // myAge is now 8 because it is 16 / 2
myAge -= 4 // myAge is now 4 because it is 8 - 4
myAge *= 3 // myAge is now 12 again because it is 4 * 3

The pattern is this

varable-name sign= value

The sign can be any one of +, -, * or /. The sign must be followed by an equals sign. There should not be a space before the equals sign.

This pattern always changes value of the variable-name.

This pattern only works for the integer, int, or floating point, float64 types.

Increase or Decrease by One

There is a special case. If you want to increase the value of a variable you can do it like this:

var myAge int
myAge++

This is also the same as myAge += 1 and myAge = myAge + 1. There is a corresponding special case to decrease a number by one. It looks like this:

var myAge int
myAge--

In both cases the value of the variable will only change by one. You cannot change it by another number.

The pattern also only works for the integer, int, or floating point, float64 types.

Information

The typical use case for the last tip is in the post-statement of a for loop. You will normally see a for loop written like this:

var candidateNumber int
for candidateNumber = 2; candidateNumber <= squareRootOfUpperLimit; candidateNumber++ {
    // the body of the for loop....
}

This for loop was taken from the Sieve of Eratosthenes program.

Another Use for the initialise-statement

The initialise-statement that you can use as the first part of a for loop, can also be used in a if statement.

The revised if statement pattern looks like this:

if initialise-statement; condition {
    statements-to-execute
}

Just like the initialise-statement in a for loop, the initialise-statement when used in an if statement is executed before the condition is tested. As before if the condition is true then the statements-to-execute are executed. If the condition is false, then the statements-to-execute are skipped over and execution continues after the last brace, }.

The initialise-statement must be separated from the condition by a semicolon, a ;.

Information

Remember you don’t have to use this form of an if statement. The initialise-statement and the following semicolon, ; are entirely optional.

You can continue to use the simpler form of an if statement if you find that form easier to understand.

String Joins

break/continue


In the last lesson we looked at the how loops work and the pattern Go uses for loops.

This is the pattern for a while loop, a loop that repeats while the condition at the top of the loop is true.

for condition {
    statements-to-repeat
} // last brace

Go uses the keyword for to indicate a loop, regardless of which type of loop it is. Let’s look at how this works again.

First the condition is tested before the loop starts. If the condition is false then the statements-to-repeat are skipped over and execution continues after the last brace.

Remember that loop statements contain an embedded if statement.

But, if the condition is true the statements-to-repeat are executed. Once all of the statements-to-repeat have been executed we jump back to the for line and test the condition again.

If the condition is still true the statements-to-repeat are executed again, for a second time. Once the statements-to-repeat have been executed the condition is tested yet again.

The process is repeated until the condition becomes false.

We call this a while loop because the loop goes around while the condition is true. The condition is tested before each time though the loop, including the very first time.

Looping a Fixed Number of Times

Now let’s look at a very simple extension of this idea. A loop that loops a fixed number of times.

Imagine we wanted to write a simple program that would print out the numbers from 1 to 10. If you think about this you will realise that we can do this by calling a fmt.Println function in a loop. Our program might look like this:

 1package main
 2
 3import "fmt"
 4
 5func main() {
 6	var number int
 7	number = 1
 8
 9	for number < 11 {
10		fmt.Println(number)
11		number = number + 1
12	}
13}
Fig-1. Printing the numbers 1 to 10 using a while loop pattern

If you run it you’ll see something like this:

1
2
3
4
5
6
7
8
9
10

Line 11

number = number + 1

just ensures that the value of the variable number increases by one each time around the loop.

So far so good. But we can write the loop in a different a slightly shorter form.

Type Less, Do the Same Thing

Go has a second, very closely related loop pattern. It still uses the for keyword but we can provide some extra information on the for line.

Before we look at the pattern, lets show you an example. This is the same program as the above, but this time written in the new form.

 1package main
 2
 3import "fmt"
 4
 5func main() {
 6	var number int
 7	for number = 1; number < 11; number = number + 1 {
 8		fmt.Println(number)
 9	}
10}
Fig-2. Printing the numbers 1 to 10 using a for loop pattern

If you run this program you’ll see the same output as before:

1
2
3
4
5
6
7
8
9
10

It is important to say that both the output and the logic of these two programs is identical. But we’ve now manged to write the same program in 10 lines compared to the original 13 lines.

What’s Going On

So what’s going on? Saving three lines doesn’t see like very much. The answer is actually quite a bit!

The magic all happens in one line, the revised for line. So let’s look at it again. Here’s the revised loop.

for number = 1; number < 11; number = number + 1 {
	fmt.Println(number)
}

So lets start with the part you already know. The middle part. The number < 11 between the two semicolons, the ; (typed ;) is the condition part of the for loop. This behaves as the exactly as before. So, the condition is tested each time around the loop, including the first time. If the condition is true, the loop executes. In this case we execute the fmt.Println(number) line to print the value of the variable number. If the condition is false then the loop stops and we don’t print anything.

Now lets look at the bit on the end of the for line, the bit after the last ;. It’s just number = number + 1. If you look back at the original program, you can see we have just moved line 11 in the original program up. This is called the post statment in Go. The post statement is executed each time though the loop, after the loop body, but before the condition is tested again. So when the loop condition is true we we execute the fmt.Println(number) line to print the value of the variable number. Then we jump up to the post statement and execute that to increase the value of number by one. Only after the post statement has executed do we retest the condition.

This is exactly the same logic as the original program. The program behaves as if the number = number + 1 bit was within the loop body, as we had in the original program.

This leaves us with the first part of the new for line, the number = 1 bit. Go calls this the initialisation statement. The initialisation statement is executed just once, before the condition is first tested.

The for loop Pattern

The pattern for a for loop is:

for initialise-statement; condition; post-statement {
    statements-to-repeat
} // last brace

Important

The semicolons, the ; are always required, so you can’t leave them out. Also the entire for statement needs to be on one line.

The pattern works like this. First the initialise-statment is executed. Next before the loop starts the condition is tested. If the condition is false then the statements-to-repeat are skipped over and the post-statement is never executed. Execution continues after the last brace.

If the condition is true the statements-to-repeat are executed. Once all of the statements-to-repeat have been executed we jump back to the for line.

We next execute the post-statement and then test the condition again.

If the condition is still true the statements-to-repeat are executed again, for a second time. Once the statements-to-repeat have been executed the post-statement is executed again before the condition is retested.

The process is repeated until the condition becomes false.

Now it is your turn

Lets see if you can work out what this program does:

 1package main
 2
 3import "fmt"
 4
 5func main() {
 6	var counter int
 7	for counter = 0; counter < 21; counter = counter + 2 {
 8		fmt.Print(counter)
 9		fmt.Print(", ")
10	}
11	fmt.Println()
12	fmt.Println("=======================================")
13	for counter = 99; counter > 79; counter = counter - 2 {
14		fmt.Print(counter)
15		fmt.Print(", ")
16	}
17	fmt.Println()
18}
<figcaption class = "text-center">
    
    Fig-3. What does this program do?
</figcaption>

See if you can also rewrite line 12, the

	fmt.Println("=======================================")

line using a loop.

It’s easy. The first loop, that starts at line 7 prints out all of the even numbers from zero to 20. Notice how the value of counter increases by 2 each time around the loop. Computers consider zero as an even number.

Line 12 prints a row of =’s signs using a single fmt.Println() line.

The second loop, that starts at line 13 prints out all of the odd numbers for 99 down to 81, going backwards. Notice how this time counter gets smaller by 2 each time around the loop.

Look at line 12 closely. How many = can you count in the fmt.Println() statement? Now use this number to create a new loop to print out exactly the number of =’s that you require. You need to copy the pattern of the for loop in the program shown in Fig-2.

To Infinity and Beyond

Before we move on, lets take a quick look an infinite loops. An infinite loop is just that, a loop that goes on forever and ever. Once the program enters the loop, it will never stop.

The pattern is simply:

for {
    statements-to-repeat
} // last brace

It is just a for statement without any condition, or initialisation statement, or post-statement. It works like this.

As soon as the for statement is reached, the program executes the statements-to-repeat block. Once it reaches the last brace, it jumps back up to the for line and starts executing the statements-to-repeat for a second time

This process continues forever.

Just for fun let’s write an infinite loop program.

 1package main
 2
 3import "fmt"
 4
 5func main() {
 6	var lineNumber int
 7	lineNumber = 1
 8	for {
 9		fmt.Print("Line number: ")
10		fmt.Println(lineNumber)
11		lineNumber = lineNumber + 1
12	}
13}
Fig-4. An infinite loop

When you run this program you will see something like this:

Line number: 1
Line number: 2
Line number: 3
Line number: 4
Line number: 5
Line number: 6
Line number: 7
Line number: 8
Line number: 9
Line number: 10
...

The list will rapidly scroll of the top of the screen!

Stopping the infinite loop program

The only way to stop the infinite loop program is to “break” it. You can do this by typing CRTL+c in the console window where the program is running.

The output will be something like this:

...
Line number: 196258
^CLine number: 196259
Line number: 196260
Line number: 196261
Line number: 196262
Line number: 196263
exit status 2

The ^C is where the CRTL+c was typed. It’s not unusual for the output to continue for a little bit after this point.

Important

Programmers very rarely write infinite loops deliberately. They are almost always a mistake in your program. This mistake is always in the condition of the loop. The mistake is that for some reason the result of the condition is always true so the loop never stops.

Putting it Altogether - the sieve program

Time to put all of your new loops knowledge to good use. We are going to write a program to find all of the prime numbers up to a maximum limit in this case 10,000.

Remember that a prime number is a number greater than one that can only be divided only be one or itself.

Why are we looking at prime numbers? Three reasons. Firstly, prime numbers are important in computer science, especially in cryptography to keep messages and data private. People use this all of time, for example, when someone buys you something on the internet.

Secondly, the approach we are going to use makes in interesting example of a for loop.

Lastly, just because it’s one of the Go example problems. See the information box for more details.

Information

A prime number generator is one of the famous Go examples. You can find the original one on the Go Playground. You can even run it on the website.

This program has a lot of interesting, and complex Go things happening in it. We are going to write a much simpler version.

How are we going to do this? Well its not as hard as you think. First we need a list of numbers starting at 2. Lets try between 2 and to 20

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

None of the even numbers can be primes, as they all divide by 2, apart from 2 itself. So we need to take those out of the list. This leaves

3 5 7 9 11 13 15 17 19

Now we need to take the next smallest number still in the list. That’s 3 and remove any multiples of 3 form the list. This leaves

3 5 7 11 13 17 19

Now we repeat the process. The next smallest number is 5, so we wnat to remove any multiples of 5 form the list. But there are none to remove. The 10 and 15 have already been removed for by previous steps. This makes sense if you remember that 5 * 5 = 25. And 25 is larger than the biggest number we had in the list at the start. So we are finished and the final list of primes up to 20 is:

3 5 7 11 13 17 19

This approach is know as the Sieve of Eratosthenes. You can see it in action by looking at the animation.

Fig-5: An animation of the Sieve of Eratosthenes. Thanks to Wikipedia

The Program

Now you know what the idea is, lets look at the program.

 1package main
 2
 3import (
 4	"fmt"
 5	"math"
 6
 7	"github.com/gophercoders/simpleio"
 8)
 9
10func main() {
11	var upperLimit int
12	upperLimit = 2
13	fmt.Print("Enter a number between 2 and 10,000: ")
14	upperLimit = simpleio.ReadNumberFromKeyboard()
15
16	// This is the first trick
17	// The || means OR. If the upper limit is > than 10000,
18	// OR the upper limit is < 2 then the number is out of range.
19	// If EITHER condition is true then user typed in a number that is out
20	// within the range of valid numbers that we need. In this case we need
21	// to ask them again until they do enter a number that is within
22	// the range we need.
23	for upperLimit < 2 || upperLimit > 10000 {
24		fmt.Print("Enter a number between 2 and 10,000: ")
25		upperLimit = simpleio.ReadNumberFromKeyboard()
26	}
27	var squareRootOfUpperLimit int
28	squareRootOfUpperLimit = int(math.Sqrt(float64(upperLimit)))
29
30	// This is the second trick
31	// We need to create a BIG list of true and false values.
32	// We use something called a slice to do this.
33	// This creates the long list for us in memory.
34	// When we create it every entry in the list is set to false for us.
35	var factors []bool
36	factors = make([]bool, upperLimit+1)
37
38	fmt.Print("The prime numbers up to ")
39	fmt.Print(upperLimit)
40	fmt.Println(" are: ")
41	var candidateNumber int
42	for candidateNumber = 2; candidateNumber <= squareRootOfUpperLimit; candidateNumber = candidateNumber + 1 {
43		if factors[candidateNumber] == false {
44			fmt.Print(candidateNumber)
45			fmt.Print(" ")
46			var multiple int
47			for multiple = candidateNumber * candidateNumber; multiple <= upperLimit; multiple = multiple + candidateNumber {
48				factors[multiple] = true
49			}
50		}
51	}
52
53	for candidateNumber = squareRootOfUpperLimit; candidateNumber <= upperLimit; candidateNumber = candidateNumber + 1 {
54		if factors[candidateNumber] == false {
55			fmt.Print(candidateNumber)
56			fmt.Print(" ")
57		}
58	}
59	fmt.Println()
60}
Fig-6. The sieve.go program.

Before we talk about how this program works you need to run it. When you do that you should see something like this

Enter a number between 2 and 10,000: 120
The prime numbers up to 120 are:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113

If you look carefully at this list of prime numbers you’ll see that it matches the list of prime numbers in the animation.

If you look at the program you can see that it contains three loops. One while loop pattern between lines 23 and 26 and three for loop patterns between lines 42 and 51, 47 and 49, and 53 and 58.

There also two new things in the program which we will describe as we go along.

First Ask the User for the Upper Limit

Lets start by looking at lines 11 to 14. Our first task is to ask the user what the maximum number should be.

var upperLimit int
upperLimit = 2
fmt.Print("Enter a number between 2 and 10,000: ")
upperLimit = simpleio.ReadNumberFromKeyboard()

We only want to know the prime numbers up to some maximum number. This maximum number is stored in the upperLimit variable. Then we use the output pattern to ask the user what the number should be. Followed by the input pattern to read the maximum number that the user typed in.

Now we come to the first loop, the while loop pattern. Lets look at lines 23 to 26 more closely.

for upperLimit < 2 || upperLimit > 10000 {
    fmt.Print("Enter a number between 2 and 10,000: ")
    upperLimit = simpleio.ReadNumberFromKeyboard()
}

This is just while loop pattern, but this time the condition part is more complex. To explain this let’s think about what we want the program to do when the user enters a value for upperLimit.

We know from maths that zero and one are not prime numbers. So if the user typed in 1 for the upperLimit we know this is a mistake. If the user does this we know we have to ask the user to type in a new number. We want the same thing to happen if the user types in zero.

We also know from maths that a prime number must be a positive number. So we also have to reject any negative numbers that the user types in.

If you put all of this together you end up with a condition like this:

upperLimit < 2

This checks the lower limit that we asked the user to type a number between. But we also have an upper limit that we need to check.

The upper limit that we asked the user to type in must not exceed 10,000. We have to check this which gives us a condition like this:

upperLimit > 10000

Now comes the new part, the first trick. If just one of these conditions is true then we know the user must have typed a number that is outside of the range of numbers we want. In this case we have to ask the user to type the number in again.

We can do this by combining the results of each of the condition tests. To do this we use a logical OR operation. This is typed ||, SHIFT+ \ typed twice. The logoical OR works like this.

It tries the first condition, the upperLimit < 2 part. If this is true, then it executes the loop, which asks the user to type in the number again.

If the first condition, upperLimit < 2 is false, then it tries the second condition, the upperLimit > 10000. If this condition is true then it executes the loop.

If the second condition is, upperLimit > 10000 is also false, then both conditions were false and the loop is skipped completely. If the loop is skipped completely, then upperLimit must be within the range we need, 2-10,000 (inclusive).

Like any loop, the condition, or more correctly in this case, both conditions, are checked again. Only when both conditions are false is the loop skipped.

The overall effect is to keep asking the user to type in a number until they they type one in that is within the range, but only if the number they typed initially was outside of the range.

Don't Panic!

Don’t panic, if you don’t fully understand this. Just trust that it means that the condition in the for is true, so the loop will run, if either of the two tests is true.

We are going talk about logical operators and how to use them in a later lesson. We’ll explain things fully then.

Then We Add an Optimisation

The next lines of interest are lines 27 and 28

var squareRootOfUpperLimit int
squareRootOfUpperLimit = int(math.Sqrt(float64(upperLimit)))

If we know what the square root of the upperLimit is we can use this to make the program run faster by performing less calculations. This is called an optimization.

The square root of number is the number which when multiplied by itself gives you the original number back. For example the square root of 9 is 3, because 3 × 3 = 9. For 16 it’s 4, for 25 it’s 5.

Line 42 uses the Sqrt function from the math package to work out the square root for the upper limit. The Sqrt function expects a floating point number to be passed to it. So, we have to convert the integer number to a floating point number using a type conversion. The type conversion is the

float64(upperLimit)

part. We are converting to a floating point type, a float64 the value of upperLimit which we defined earlier as an int, integer number type.

The answer of the Sqrt function is also a floating point, float64 type. But we only want the integer part of the answer. We want to throw away everything after the decimal point. This is called truncating the number. We do this with another type conversion, this time converting to an int type. This type conversion is the

int(math.Sqrt(...))

part. Putting both conversions together in one line and adding the variable assignment gives you the final from:

squareRootOfUpperLimit = int(math.Sqrt(float64(upperLimit)))

We’ll explain how we use the square root when we talk about the first for loop pattern starting on line 42.

Then We Make a Long List

This takes us to the next trick on lines 35 and 36.

var factors []bool
factors = make([]bool, upperLimit+1)

We need to have a list numbers that we can mark as prime or not prime. This is how we achieve this. Except, we don’t have a list of numbers. We use a list were each element in the list is either true, meaning it has factors, so its not a prime, or false meaning, it has not factors so it is not a prime number. Go has a special type of these true or false values called bool. The numbers are represented by the position in this list.

Lets take the numbers 0, 1, 2, 3 and 4 as the examples. The list always starts at zero. We know that zero is not a prime number. So we want the list at position zero to be true. We also know that one is not a prime number so we want the list at position one to also be true. But two is different. It is a prime number so we want the list at position 2 to be false. Three is also prime, so it’s position should be false. Four is a multiple of two, so it’s position should be true.

If we use T for true and F for false we want the list to start like this:

Position01234
Has factors?TTFFT

Be Careful

The list contains a list of all numbers up to the upperLimit. If a number has factors, then its position in the list is marked as true. The number cannot be prime. If the number has no factors then it is prime, so it is marked as false.

At the end of the process, any numbers, which are still marked false are the prime numbers.

So how do we do this? Line 35 is the first part

var factors []bool

It says to create a variable called factors that is a list, or as Go calls it a slice, that can only hold the values true or false. We don’t yet tell Go how big we want to make this slice. The [] just means we want a slice and not a single variable of type bool

Then on line 36

factors = make([]bool, upperLimit+1)

we tell Go how large we want the slice to be using the special make function. We tell Go to make the slice one bigger than upperLimit. We need to be one bigger because we have to count zero. So if upperLimit was 120 we want a slice with 121 elements in it, numbered 0,1,2,3,4…. all the way up to …119,120.

Make also needs to know what type we want to create because it can be used to create different types. So we have to tell it that we want a slice of bool types with the []bool bit.

Don't Panic!

Don’t panic, if you don’t fully understand this. Just think of factors as a very long list, that can only contain true, or false at each position in the list. Just like the table above, but bigger. This is all you need to understand how the sieve program works.

We’ll be talking more about slices, and how to use them in a later lesson. We’ll explain things fully then.

Then We Sieve The Numbers

Now that we have everything we need setup, we can start to look for the prime numbers. This uses a for loop pattern and happens on lines 41 to 51.

var candidateNumber int
for candidateNumber = 2; candidateNumber <= squareRootOfUpperLimit; candidateNumber = candidateNumber + 1 {
    if factors[candidateNumber] == false {
        fmt.Print(candidateNumber)
        fmt.Print(" ")
        var multiple int
        for multiple = candidateNumber * candidateNumber; multiple <= upperLimit; multiple = multiple + candidateNumber {
            factors[multiple] = true
        }
    }
}

This is how we remove all of the numbers that are not primes from the list. Let’s walk through the code to explain it.

candidateNumber is the number we want to test to see if it is a prime. It is also the position in the slice.

Let’s imagine that the upperLimit was 16. So the square root of 16 is 4.

So we start with candidateNumber = 2, and we know 2 is less than 4. The test candidateNumber <= squareRootOfUpperLimit is true so we start to execute the loop.

We know that the slice intially contains false at every position. The if statement condition, factors[candidateNumber] == false becomes factors[2] == false and is true. The number inside the square brackets, [ and ] just means give me the value in the slice at this position. So, [2] means give me the value in the slice at position number 2. This is really the third element in the slice if you look at the table above.

This condition is true. So we print out the candidateNumber because we know it is prime.

The Nested Loop

Now we need to take out any multiples of the candidateNumber. These numbers cannot be prime numbers because they are factors of the candidateNumber.

To do this we need another loop, inside, or nested, within this loop. This nested loop uses a for pattern and looks like this:

var multiple int
for multiple = candidateNumber * candidateNumber; multiple <= upperLimit; multiple = multiple + candidateNumber {
    factors[multiple] = true
}

This is how we remove the multiples, the non prime, numbers from the slice.

The loop starts at the first multiple of the candidateNumber which is the candidate number squared, candidateNumber * candidateNumber. This is the initial value of multiple. If candateNumber was 2 then multiple starts with the value 4.

The loop runs until the the value of multiple exceeds the upperLimit. This means the loop will stop when we try to go beyond the end of the slice.

multiple is 4 and this is less than 16, the value of upperLimit so the loop executes. Inside the loop we set the slice at position multiple, which is 4, to true to indicate that the the number, 4, is not prime.

Not we reach the for loops post statement. This increases the value of multiple by the candiateNumber to give you the next multiple. So when multiple is 4 and candidateNumber is 2 the new value of multiple is 6.

The process then repeats.

If you continue to work this out for the following loop iterations, you will see that this marks the numbers 4, 6, 8, 10, 12, 14 and 16 to true

We are relying on this inner loop to mark all the multiples of the candidateNumber all the way to the end of the slice. The condition in the loop

multiple <= upperLimit

ensures that this is the case.

Once the inner loop has completed, all of the multiples of the candidateNumber have been removed. This also completes a loop iteration of the outer loop.

Now Back To the Outer Loop

The program now jumps back to the top of the outer loop, on line 42, and executes the for loops post statement:

candidateNumber = candidateNumber + 1

This increases the candidate number. The for loops condition of

candidateNumber <= squareRootOfUpperLimit

is then retested. If this is true, then the loop body runs and attempts to remove multiples of the next candidateNumber which is not already marked as false.

Back to squareRootOfUpperLimit and the Optimisation

We use squareRootOfUpperLimit speed things up by reducing the number of times the outer loop runs. Lets explain this with an example. If we assume that the value of upperLimit was 100, the the square root of 100 is 10.

If we pretend that the outer for loop looked like this:

for candidateNumber = 2; candidateNumber <= upperLimit; candidateNumber = candidateNumber + 1 {
    // everything inside the loop is unchanged
}

then this loop goes around 100 - 2 + 1, or 99 times. Remember there are 101 elements in the list because we need to count the zero.

But that 99 is much larger than the 10 - 2 + 1, or 9 times that we would need if we used the square root of the upper limit.

So the computer has more work to do.

Now if we look at the test of the inner for loop

for multiple = candidateNumber * candidateNumber; multiple <= upperLimit; multiple = multiple + candidateNumber {
    // everything inside the loop is unchanged
}

when candidateNumber reaches 11, the initial value of multiple, as calculated by the loops initalise statement is 11 * 11, or 121.

But 121 is larger than the value of upperLimit which is 100. So the condition in the for loop is always false when candidateNumber is larger then 10, the square root of 100. But the computer always has to do the multiplication and assignment to multiple and then the test to find this out.

This all takes tiny amounts of time. But if we have to do this 99 times, the number of times that the outer loop goes around this all adds up.

So the less things we ask the computer to do, in other words the less instructions the computer has to execute, the faster the program runs.

In this case the optimised version, the version we have used, that uses the squareRootOfUpperLimit is about three times faster! That’s why we need to work out and use the squareRootOfUupperLimit.

Finally We Just Print the Remaining Primes

The final part of the of the program is really easy. It’s just the last for loop on lines 53 - 58. This is another for loop pattern.

for candidateNumber = squareRootOfUpperLimit; candidateNumber <= upperLimit; candidateNumber = candidateNumber + 1 {
    if factors[candidateNumber] == false {
        fmt.Print(candidateNumber)
        fmt.Print(" ")
    }
}

This loop just looks at at every element in the slice from position squareRootOfUpperLimit until the end. If the element is marked as false then the program prints out the position of the element, the candidateNumber, followed by a space.

The loops initialise statement sets candidateNumber equal to squareRootOfUpperLimit. The post statement in the loop increases the value of candidateNumber by one on each iteration.

Search

Featured Lesson

Numbers

What You are Going to Learn?

Computers are used to process data. All data is made up of numbers. Yes, really! Everything is just a bunch of numbers to a computer. These are the only things they understand.

We are going to explain how numbers are used in Go programs. Then we are going to show you how to do type sums in Go.