Project Euler - 012

icymirror

Problem 012:
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?

问题12：
三角数序列是通过连续的加自然数得到的。比如第七个三角数是： 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28。
而前十个三角数依次是：1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
下面，让我们列出前七个三角数的因数：
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
我们可以看到，28是第一个有超过5个因数的三角数。
那么，第一个有超过500个因数的三角数是几？

代码：

1. 
   
2. package main
   
3. 
   
4. import (
   
5.         "fmt"
   
6. )
   
7. 
   
8. func BuildPrimeFactorTable(scope int) ([]int) {
   
9.         result := make([]int, 0)
   
10.         if scope < 2 {
    
11.                 return result
    
12.         }
    
13.        
    
14.         result = append(result, 2)
    
15.         for number := 3; number < scope + 1; number += 2 {
    
16.                 if IsPrime(number) {
    
17.                         result = append(result, number)
    
18.                 }
    
19.         }
    
20.        
    
21.         return result
    
22. }
    
23. 
    
24. func PrimeFactorization(number int, primes []int) (map[int]int) {
    
25.         result := make(map[int]int)
    
26.         for _, prime := range primes {
    
27.                 for {
    
28.                         if number % prime == 0 {
    
29.                                 if _, exist := result[prime]; exist {
    
30.                                         result[prime] = result[prime] + 1
    
31.                                 } else {
    
32.                                         result[prime] = 1
    
33.                                 }
    
34.                                 number = number / prime
    
35.                         } else {
    
36.                                 break
    
37.                         }
    
38.                 }
    
39. 
    
40.                 if number == 1 {
    
41.                         break
    
42.                 }
    
43.         }
    
44.        
    
45.         return result
    
46. }
    
47. 
    
48. func Problem012(divisorCount int) int {
    
49.         if divisorCount < 1 {
    
50.                 return 0
    
51.         }
    
52. 
    
53.         primes := BuildPrimeFactorTable(divisorCount * divisorCount)       
    
54.         base := 1
    
55.         for {
    
56.                 triNumber := (1 + base) * base / 2
    
57.                 factors := PrimeFactorization(triNumber, primes)
    
58.                
    
59.                 total_factors := 1
    
60.                 for _, value := range factors {
    
61.                         total_factors *= (value + 1)
    
62.                 }
    
63.                 if total_factors > divisorCount {
    
64.                         return triNumber
    
65.                 } else {
    
66.                         base++
    
67.                 }
    
68.         }
    
69. }
    
70. 
    
71. func main() {
    
72.         fmt.Println("Problem 012 result: ", Problem012(500))
    
73. }
    

复制代码