# Golang : How to determine a prime number?

In mathematics and computer security, it is very important to determine if a given number is a prime number or not. For this tutorial, we will learn how to find out if a number is prime or not.

For the uninitiated, a number is prime if the only divisors it has are 1 and itself.

First, we generate our own function to determine a prime number. However, it has limitation(inefficient) in determining and handling a large prime number.

Golang's standard library has good prime number generator and prime number validation functions. We will use the standard functions for the code that follows to validate large prime number (big.Int type)

Here we go!

`````` package main

import (
"crypto/rand"
"fmt"
"math/big"
)

// for small prime
func isPrime(num int) bool {
for i := 2; i < num; i++ {
if num%i == 0 {
return false
}
}
return true
}

func main() {

fmt.Println("Is 1 a prime number? : ", isPrime(1))
fmt.Println("Is 2 a prime number? : ", isPrime(2))
fmt.Println("Is 3 a prime number? : ", isPrime(3))
fmt.Println("Is 4 a prime number? : ", isPrime(4))
fmt.Println("Is 5 a prime number? : ", isPrime(5))
fmt.Println("Is 6 a prime number? : ", isPrime(6))
fmt.Println("Is 7 a prime number? : ", isPrime(7))
fmt.Println("Is 8 a prime number? : ", isPrime(8))
fmt.Println("Is 9 a prime number? : ", isPrime(9))
fmt.Println("Is 10 a prime number? : ", isPrime(10))

// for security purpose, it is good to have big prime number
// Golang's crypto/rand package has builtin prime number generator
// see https://www.socketloop.com/references/golang-crypto-rand-prime-function-example

var bigPrime *big.Int
var bits int
var err error

bits = 999

if err != nil {
fmt.Println(err)
}

fmt.Printf("Generated big prime number : %d\n", bigPrime)
fmt.Println("------------------------------------------------")
fmt.Printf("Is %d a prime number? : %v\n", bigPrime, bigPrime.ProbablyPrime(50))

// just to test how good is ProbablyPrime() function
// we create a false prime

falsePrime := new(big.Int)
// to avoid constant 554378014529860247248431469761 overflows uint64
// see https://www.socketloop.com/tutorials/golang-convert-string-or-integer-to-big-int-type

falsePrime.SetString("554378014529860247248431469761", 10) // base 10
fmt.Printf("Is %d a prime number? : %v\n", falsePrime, falsePrime.ProbablyPrime(50))

// now DO NOT use ProbablyPrime for 1, it will give wrong results
falsePrime.SetString("1", 10) // base 10
fmt.Printf("Is %d a prime number? : %v\n", falsePrime, falsePrime.ProbablyPrime(50))
fmt.Printf("Is %d a prime number? : %v\n", falsePrime, falsePrime.ProbablyPrime(2))

// but ok for 3
falsePrime.SetString("3", 10) // base 10
fmt.Printf("Is %d a prime number? : %v\n", falsePrime, falsePrime.ProbablyPrime(50))
fmt.Printf("Is %d a prime number? : %v\n", falsePrime, falsePrime.ProbablyPrime(2))

// and the rest...
falsePrime.SetString("4", 10) // base 10
fmt.Printf("Is %d a prime number? : %v\n", falsePrime, falsePrime.ProbablyPrime(50))
fmt.Printf("Is %d a prime number? : %v\n", falsePrime, falsePrime.ProbablyPrime(2))
}
``````

output:

Is 1 a prime number? : true

Is 2 a prime number? : true

Is 3 a prime number? : true

Is 4 a prime number? : false

Is 5 a prime number? : true

Is 6 a prime number? : false

Is 7 a prime number? : true

Is 8 a prime number? : false

Is 9 a prime number? : false

Is 10 a prime number? : false

Generated big prime number : 4330246321548259.....1372849

Is 4330246321548259.....1372849 a prime number? : true

Is 554378014529860247248431469761 a prime number? : false

Is 1 a prime number? : false

Is 1 a prime number? : false

Is 3 a prime number? : true

Is 3 a prime number? : true

Is 4 a prime number? : false

Is 4 a prime number? : false

NOTES:

Can you write your own functions that are more efficient and secure than those functions found in the standard package? Yes, of course you can. After all, the ProbablyPrime() function has a disclaimer that - `"it is not suitable for judging primes that an adversary may have crafted to fool this test"`.

Happy priming!

References:

https://golang.org/pkg/math/big/#Int.ProbablyPrime

https://www.socketloop.com/tutorials/golang-convert-string-or-integer-to-big-int-type

https://golang.org/src/crypto/elliptic/elliptic.go?s=871:1509#L55