Determine If A Number Is Prime Using The Go Programming Language

Almost two years ago I wrote an article explaining how to determine if a number is prime or not using JavaScript. It turns out this article became more popular than I thought it would, and if I had to guess, it might be because it is a good computer science and overall interview question for new career developers.

I thought it would make sense to revisit the post, but this time focus on accomplishing the task with the Go programming language instead of JavaScript.

In this example we’re going to explore three different approaches to getting the job done. They are certainly not the only approaches available. First we’re going to explore how to find if a particular number is prime and then we’re going to determine all the prime numbers until a certain limit value.

So what exactly is a prime number?

According to Wikipedia, a prime number can be thought of the following:

A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself.

So essentially, if you can divide a number evenly with another number that is not the value one or itself, it is not a prime number. That is good news for us because in most programming languages there is a way to see if there is a remainder value during a division operation.

Checking if a Number is Prime

Take the following function for example:

func IsPrime(value int) bool {
    for i := 2; i <= int(math.Floor(float64(value) / 2)); i++ {
        if value%i == 0 {
            return false
        }
    }
    return value > 1
}

The above function will calculate if a number is prime based on some criteria. Depending on who you ask, the number one may or may not be a prime number. I’m not a mathematician so we won’t dig too deep into that. Instead we’ll start our examination at the value two.

This is where things might get a bit interesting.

We could loop through all numbers, taking the modulus to find the remainder, up until the value that we’re checking for, but that would be very inefficient. Instead we divide the number by two to produce the halfway mark because if the loop reaches that halfway point we know that the number will not be prime. Two is the smallest number you can divide by to stand a chance at a non-prime number.

When using a modulus, if there is not a remainder, then it is not prime.

We can optimize this method a bit based on some of the feedback that I had received on the previous post that I wrote. Instead of using division, we can use the square root of the value that we’re looking for.

func IsPrimeSqrt(value int) bool {
    for i := 2; i <= int(math.Floor(math.Sqrt(float64(value)))); i++ {
        if value%i == 0 {
            return false
        }
    }
    return value > 1
}

In the above example we are only looping until the floored square root value of our number. Let’s use a numeric example to visualize this.

In a worst case let’s say we want to find if 100 is a prime number and we loop 100 times. This is improved by dividing by 2 to the halfway point giving us 50 loop iterations. However, if we were to use the square root, this would leave us with only 10 loop iterations which is much better.

This is possible because we’re only looking for the smallest possible divisor when checking if a number is prime or not. The largest possible divisor we can use is when the two divisors equal each other. More information on this can be found in the trial division section of the Khan Academy.

So we just saw how to determine whether a number is prime or not using Golang, so how about printing all the prime numbers up until a limit?

Printing Prime Numbers Using Sieve of Eratosthenes

Again, I’m no mathematician, but after browsing around on the internet I came across an algorithm for finding all the prime numbers up until a given limit. The catch here is that it will do this more efficiently than calling one of our isPrime functions within a loop. After all O(n^2) is never a good time complexity.

Sieve of Eratosthenes via Wikipedia:

A simple, ancient algorithm for finding all prime numbers up to any given limit. It does so by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the multiples of 2.

To make Sieve of Eratosthenes successful, it will have logic similar to the following:

1. Create a slice from two until the value and assign a value of true since we are going to assume everything is prime to start.
2. Take the square root of our desired value which will represent a limit to our looping.
3. Loop from two until our new square rooted limit.
4. Check to see if our current index is prime, otherwise ignore it.
5. Loop through (i * i) + ix until our initial value where x is incremental starting from value one.
6. Set every index hit to false because it is no longer a prime number.

The Golang code to match this particular algorithm can be seen below:

func SieveOfEratosthenes(value int) {
    f := make([]bool, value)
    for i := 2; i <= int(math.Sqrt(float64(value))); i++ {
        if f[i] == false {
            for j := i * i; j < value; j += i {
                f[j] = true
            }
        }
    }
    for i := 2; i < value; i++ {
        if f[i] == false {
            fmt.Printf("%v ", i)
        }
    }
    fmt.Println("")
}

The above algorithm is rated to have a time complexity of O(nloglogn) which is better than looping with O(n^2) like the previous.

Fully Functional Golang Application

Want to see all the code so you can test out the application for yourself? Below you’ll find a very simple project that will put each of these methods and functions to work.

package main

import (
    "fmt"
    "math"
)

func IsPrime(value int) bool {
    for i := 2; i <= int(math.Floor(float64(value)/2)); i++ {
        if value%i == 0 {
            return false
        }
    }
    return value > 1
}

func IsPrimeSqrt(value int) bool {
    for i := 2; i <= int(math.Floor(math.Sqrt(float64(value)))); i++ {
        if value%i == 0 {
            return false
        }
    }
    return value > 1
}

func SieveOfEratosthenes(value int) {
    f := make([]bool, value)
    for i := 2; i <= int(math.Sqrt(float64(value))); i++ {
        if f[i] == false {
            for j := i * i; j < value; j += i {
                f[j] = true
            }
        }
    }
    for i := 2; i < value; i++ {
        if f[i] == false {
            fmt.Printf("%v ", i)
        }
    }
    fmt.Println("")
}

func main() {
    for i := 1; i <= 100; i++ {
        if IsPrime(i) {
            fmt.Printf("%v ", i)
        }
    }
    fmt.Println("")
    for i := 1; i <= 100; i++ {
        if IsPrimeSqrt(i) {
            fmt.Printf("%v ", i)
        }
    }
    fmt.Println("")
    SieveOfEratosthenes(100)
}

If you run the application, you’ll see that in all three variations you get the same results. Awesome right?

Conclusion

You just saw how to determine whether or not a number is prime and print all prime numbers to a limit using the Go programming language. I previously wrote about this with JavaScript, but took this as an opportunity to make things more efficient while using a different language.

If you have a solution that is more efficient or cleaner than what I did, I encourage you to share in the comments section. It would help a lot of people learning about computer science or interviewing for software engineering jobs.

Nic Raboy

Nic Raboy is an advocate of modern web and mobile development technologies. He has experience in C#, JavaScript, Golang and a variety of frameworks such as Angular, NativeScript, and Unity. Nic writes about his development experiences related to making web and mobile development easier to understand.