🌚

Project Euler Problem 12 Solved

Posted at — Mar 28, 2014
#golang #欧拉工程 #编程

Highly divisible triangular number

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

 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
29
30
31
32
33
34
35
36
package main

import (
    "fmt"
    "math"
)

func count_divisor(num int64) int64 {
    var count, factor, lastFactor, exponent int64 = 1, 2, 0, 1

    for factor <= num {
        if math.Mod(float64(num), float64(factor)) == 0 {
            if factor == lastFactor {
                exponent++
            } else {
                count *= (exponent + 1)
                exponent = 1
                lastFactor = factor
            }
            num /= factor
        } else {
            factor++
        }
    }

    return count
}

func main() {
    var count, n int64 = 0, 1
    for count < 500 {
        n++
        count = count_divisor(n * (n + 1) / 2)
    }
    fmt.Println(n*(n+1)/2, count)
}

I’m the 99509th person to have solved this problem.