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

Problem: 

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

Solution:

First we do prime factorization of the number . Then we calculate the number of divisors according to the result of prime factorization .

12375th triangle number: 76576500

number of divisors: 576

Run Code on Go Playground

```package main

import (
"fmt"
)

// 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; ok {
pfs += 1
} else {
pfs = 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
}

// 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
}

// return n-th triangular number
func TriangularNumber(n int) int {
return n * (n + 1) / 2
}

func main() {
for i := 1; i < 100000; i++ {
n := TriangularNumber(i)
nn := NumberOfDivisors(n)
if nn >= 500 {
fmt.Print(i)
fmt.Print("-th ")

fmt.Print(n)
fmt.Print(": ")
fmt.Println(nn)
break
}
}
}
```

Tested on: Go Playground

References: