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
bigPrime, err = rand.Prime(rand.Reader, bits)
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
// we use SetString instead
// 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
See also : Golang : Check if integer is power of four example
By Adam Ng
IF you gain some knowledge or the information here solved your programming problem. Please consider donating to the less fortunate or some charities that you like. Apart from donation, planting trees, volunteering or reducing your carbon footprint will be great too.
Advertisement
Tutorials
+13.2k Golang : On enumeration
+16.5k Golang : How to log each HTTP request to your web server?
+5.2k Golang : Create new color from command line parameters
+19.8k Golang : For loop continue,break and range
+10.8k Golang : Convert a rune to unicode style string \u
+33.7k Golang : Strip slashes from string example
+12.5k Golang : unknown escape sequence error
+3.7k Mac OSX : Get disk partitions' size, type and name
+14.9k Golang : Generate QR codes for Google Authenticator App and fix "Cannot interpret QR code" error
+3.8k Nginx and PageSpeed build from source CentOS example
+11.2k Golang : Listen and Serve on sub domain example
+4.4k Javascript : How to loop over and parse JSON data?