[Golang] Get All Prime Factors of Integer Number
Prime Factorization - Find all prime factors of a given integer number in Go programming language.
The prime factorization algorithm comes from GeeksforGeeks [1]. Please go there for details of the algorithm and explanation.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | package pfs
// Get all prime factors of a given number n
func PrimeFactors(n int) (pfs []int) {
// Get the number of 2s that divide n
for n%2 == 0 {
pfs = append(pfs, 2)
n = n / 2
}
// n must be odd at this point. so we can skip one element
// (note i = i + 2)
for i := 3; i*i <= n; i = i + 2 {
// while i divides n, append i and divide n
for n%i == 0 {
pfs = append(pfs, i)
n = n / i
}
}
// This condition is to handle the case when n is a prime number
// greater than 2
if n > 2 {
pfs = append(pfs, n)
}
return
}
|
Testing:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | package pfs
import (
"fmt"
"testing"
)
func TestPrimeFactors(t *testing.T) {
if fmt.Sprintf("%v", PrimeFactors(23)) != `[23]` {
t.Error(23)
}
if fmt.Sprintf("%v", PrimeFactors(12)) != `[2 2 3]` {
t.Error(12)
}
if fmt.Sprintf("%v", PrimeFactors(360)) != `[2 2 2 3 3 5]` {
t.Error(360)
}
if fmt.Sprintf("%v", PrimeFactors(97)) != `[97]` {
t.Error(97)
}
}
|
Tested on:
- Ubuntu Linux 17.04, Go 1.8.1
- Go Playground
References:
[1] | Efficient program to print all prime factors of a given number |
[2] | go - Checking the equality of two slices - Stack Overflow |