# ×î½ü·ÃÎÊ°å¿é ²é¿´: 1239 | »Ø¸´: 0

# [ÆäËû] Project Euler - 012 [¸´ÖÆÁ´½Ó]

ÂÛÌ³»ÕÕÂ:
4     ·¢±íÓÚ 2015-09-29 11:25 |ÏÔÊ¾È«²¿Â¥²ã
 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)) } ¸´ÖÆ´úÂë
 ÄúÐèÒªµÇÂ¼ºó²Å¿ÉÒÔ»ØÌû µÇÂ¼ | ×¢²á ±¾°æ»ý·Ö¹æÔò ·¢±í»Ø¸´ »ØÌûºóÌø×ªµ½×îºóÒ»Ò³ DTCC2020ÖÐ¹úÊý¾Ý¿â¼¼Êõ´ó»á ÏÞÊ±8.5ÕÛ