# [Golang] Calculate Number of Divisors

Assume *n* is a natural number, calculate the number of divisors of
*n*.

Let the prime factorization of *n* be:

n=p_{1}^{a1}×p_{2}^{a2}× ... ×p_{k}^{ak}

number of divisors of n is:

(a_{1}+ 1)(a_{2}+ 1)...(a_{k}+ 1)

## Prime Factorization

The following code will return prime factorization of a given number n:

```
// Prime factorization of a given number
//
// A map is returned.
//
// key of map: prime
// value of map: prime exponents
//
func PrimeFactorization(n int) (pfs map[int]int) {
pfs = make(map[int]int)
// Get the number of 2s that divide n
for n%2 == 0 {
if _, ok := pfs[2]; ok {
pfs[2] += 1
} else {
pfs[2] = 1
}
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 {
if _, ok := pfs[i]; ok {
pfs[i] += 1
} else {
pfs[i] = 1
}
n = n / i
}
}
// This condition is to handle the case when n is a prime number
// greater than 2
if n > 2 {
pfs[n] = 1
}
return
}
```

## Number of Divisors

Based on the result of prime factorization of previous section, we can calculate number of divisors of a given number n as follows:

```
// Calculate number of divisors of a given number
func NumberOfDivisors(n int) int {
pfs := PrimeFactorization(n)
num := 1
for _, exponents := range pfs {
num *= (exponents + 1)
}
return num
}
```

See [1] for more details.

## Application

The problem 12 of Project Euler is about finding the number of divisors of triangular number. See [4] for more details.

Tested on: Go Playground

References:

[1] |

[2] | [Golang] Get All Prime Factors of Integer Number |

[3] | [Golang] Sum of the Proper Divisors (Factors) |

[4] | [Golang] Highly Divisible Triangular Number - Problem 12 - Project Euler |