工学1号馆

home

Project Euler 12–Highly divisible triangular number

Wu Yudong    November 10, 2017     欧拉计划   549   

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?

三角形数序列是由对自然数的连加构造而成的。所以第七个三角形数是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个约数的三角形数是多少?

#include <stdio.h> 
#include <stdbool.h>

int trinumber(int n)
{
    if(n % 2 == 0) {
        return (n / 2) * (n + 1);
    } else {
        return ((n + 1) / 2) * n;
    }
}

bool divnum(int n)
{
    int i, sum = 0;
    for(i = 1; i * i < n; i++) {
        if(n % i == 0) {
            sum += 2;
        }
    }
    if(i * i == n) sum++;
    if(sum > 500) return true;
    else return false;
}

void solve(void)
{
    int i, num;
    num = 0;
    for(i = 1; ; i++) {
        if(divnum(trinumber(i))) {
            printf("%d\n",trinumber(i));
            break;
        }
    }
}

int main(void)
{
    solve();
    return 0;
}

 Answer:76576500
Completed on Sun, 17 Nov 2013, 12:53

如果文章对您有帮助,欢迎点击下方按钮打赏作者

Comments

No comments yet.
To verify that you are human, please fill in "七"(required)