- 论坛徽章:
- 4
|
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个因数的三角数是几?
代码:
- package main
- import (
- "fmt"
- )
- func BuildPrimeFactorTable(scope int) ([]int) {
- result := make([]int, 0)
- if scope < 2 {
- return result
- }
-
- result = append(result, 2)
- for number := 3; number < scope + 1; number += 2 {
- if IsPrime(number) {
- result = append(result, number)
- }
- }
-
- return result
- }
- func PrimeFactorization(number int, primes []int) (map[int]int) {
- result := make(map[int]int)
- for _, prime := range primes {
- for {
- if number % prime == 0 {
- if _, exist := result[prime]; exist {
- result[prime] = result[prime] + 1
- } else {
- result[prime] = 1
- }
- number = number / prime
- } else {
- break
- }
- }
- if number == 1 {
- break
- }
- }
-
- return result
- }
- func Problem012(divisorCount int) int {
- if divisorCount < 1 {
- return 0
- }
- primes := BuildPrimeFactorTable(divisorCount * divisorCount)
- base := 1
- for {
- triNumber := (1 + base) * base / 2
- factors := PrimeFactorization(triNumber, primes)
-
- total_factors := 1
- for _, value := range factors {
- total_factors *= (value + 1)
- }
- if total_factors > divisorCount {
- return triNumber
- } else {
- base++
- }
- }
- }
- func main() {
- fmt.Println("Problem 012 result: ", Problem012(500))
- }
复制代码 |
|