ProjectEuler Problem 12: Highly divisible triangular number

Mar 18, 2014

Coding

Problem 12: Highly divisible triangular number #

https://projecteuler.net/problem=12

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?

分析 #

第一个拥有500+ 个因子的三角数。

从小到大，判断每个三角数是否有超过500个因子，一旦发现，则返回。关键点是因子数目的统计！

方法1 遍历寻找 #

对于三角数n, 如果n = a*b, a in range(1, n), 则a和b均是其因子

如果 a<b, 则总因子数+2
如果 a==b, 则总因子数+1
如果 a>b, 说明寻找已经结束了，因为此时找到的 (a,b) 已经和(b,a) 重复了

C++ #

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

//判断数num，是否有超过500个因子
int isOver500Divisors(int64_t n)
{
    int cnt=0;
    for(int64_t a=1; a*a <= n; a++){
        if (n%a != 0) continue;
        
        // a is a factor
        int64_t b = n/a; // n = a * b
        if(a < b) cnt += 2; // find two factors, a and b
        if(a == b) cnt ++;  // find one factor, a
        if(a > b) break; // 据对称性，a>b时，说明已经找完了，后面再找无非是找a=n/b
    }

    return (cnt > 500)? 1:0;
}

int main()
{
    int64_t triangleNumber = 0;
    for(int64_t i=1; ;i++){
        triangleNumber += i;
        if(isOver500Divisors(triangleNumber)) break;
    }

    printf("%lld\n",triangleNumber);
    return 0;
}

Golang #

package main

import "fmt"

// 判断数num，是否有超过500个因子
func isOver500Divisors(n int64) bool {
	cnt := 0
	for a := int64(1); a*a <= n; a++ {
		if n%a != 0 {
			continue
		}

		// a is a factor
		b := n / a // n = a * b

		if a < b {
			cnt += 2 // find two factors, a and b
		}

		if a == b {
			cnt++ // find one factor, a
		}

		if a > b {
			break // 据对称性，a>b时，说明已经找完了，后面再找无非是找a=n/b
		}
	}

	if cnt > 500 {
		return true
	}
	return false
}

func main() {
	triangleNumber := int64(0)
	for i := int64(1); ; i++ {
		triangleNumber += i
		if isOver500Divisors(triangleNumber) {
			break
		}
	}

	fmt.Println(triangleNumber)
}

Python #

from math import sqrt
def isOver500Divisors(n):
    cnt = 0
    for a in range(1,int(sqrt(n))+1):
        if n % a == 0:
            b = n / a
            if a < b:
                cnt += 2 # two factors, a and b
            if a == b:
                cnt += 1 # one factor, a
            if a > b:
                break
    if cnt > 500:
        return True
    return False

i, sum = 1, 0
while True:
    sum += i
    if isOver500Divisors(sum):
        print(sum)
        break
    i += 1

答案 #

76576500