Problem 12 Highly divisible triangular number

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) 重复了

CPP

#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

作者:JarvisChu
原文链接:Problem 12 Highly divisible triangular number
版权声明:自由转载-非商用-非衍生-保持署名 | Creative Commons BY-NC-ND 3.0

发表评论