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：
三角數(shù)序列是通過連續(xù)的加自然數(shù)得到的。比如第七個(gè)三角數(shù)是： 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28。
而前十個(gè)三角數(shù)依次是：1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
下面，讓我們列出前七個(gè)三角數(shù)的因數(shù)：
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是第一個(gè)有超過5個(gè)因數(shù)的三角數(shù)。
那么，第一個(gè)有超過500個(gè)因數(shù)的三角數(shù)是幾？

代碼：

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

復(fù)制代碼