[Golang] Sum of the Proper Divisors (Factors)
Calculate the sum of all proper divisors (factors) of an integer number in Go programming language.
The steps:
- Given a natural number n, perform prime factorization of n. [3]
- Use the formula from [2] to calculate sum of all divisors (factors) of n.
- Get sum of proper divisors by subtracting n from the sum of step 2.
package main
import (
"fmt"
)
// 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
}
// return p^i
func Power(p, i int) int {
result := 1
for j := 0; j < i; j++ {
result *= p
}
return result
}
// formula comes from https://math.stackexchange.com/a/22723
func SumOfProperDivisors(n int) int {
pfs := PrimeFactors(n)
// key: prime
// value: prime exponents
m := make(map[int]int)
for _, prime := range pfs {
_, ok := m[prime]
if ok {
m[prime] += 1
} else {
m[prime] = 1
}
}
sumOfAllFactors := 1
for prime, exponents := range m {
sumOfAllFactors *= (Power(prime, exponents+1) - 1) / (prime - 1)
}
return sumOfAllFactors - n
}
func main() {
fmt.Println(SumOfProperDivisors(220))
fmt.Println(SumOfProperDivisors(284))
}
Tested on: Go Playground
References:
[1] |
[2] | Is there a formula to calculate the sum of all proper divisors of a number? - Mathematics Stack Exchange |
[3] | [Golang] Get All Prime Factors of Integer Number |
[4] | [Golang] Integer Exponentiation |