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
+5k Golang : Print instead of building pyramids
+4.7k Golang : PGX CopyFrom to insert rows into Postgres database
+11k Golang : Fix fmt.Scanf() on Windows will scan input twice problem
+5.2k Golang : Get S3 or CloudFront object or file information
+8.2k PHP : How to parse ElasticSearch JSON ?
+18.3k Golang : Generate thumbnails from images
+8.2k Golang : How to check variable or object type during runtime?
+13.2k Golang : Read XML elements data with xml.CharData example
+9.2k Golang : Changing a RGBA image number of channels with OpenCV
+4.4k Adding Skype actions such as call and chat into web page examples
+7k Ubuntu : connect() to unix:/var/run/php5-fpm.sock failed (13: Permission denied) while connecting to upstream
+9.6k Golang : Resumable upload to Google Drive(RESTful) example