Problem 12

Problem Statement

The sequence of triangle numbers is generated by adding the natural numbers. So the 7^{th} 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: 13: 1,36: 1,2,3,610: 1,2,5,1015: 1,3,5,1521: 1,3,7,2128: 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?

Approach

C++ implementation

```
````#include <stdc++.h> `

`using namespace std;`

`int numfactors(int n) {`

` int sum = 0;`

` int high = n;`

` int low = 1;`

` while(high > low) {`

` if (n % low == 0) {`

` sum += 2;`

` high = n / low;`

` }`

` low++;`

` }`

` return sum;`

`}`

`vector` next_triangle(vector in) {

` in[1] = in[1]+in[0];`

` in[0]++;`

` return in;`

`}`

`int main() {`

` `

` vector` curr(2);

` curr.push_back(1);`

` curr.push_back(1);`

` while(numfactors(curr[1]) < 500) {`

` curr = next_triangle(curr);`

` }`

` cout << curr[1] << endl;`

` return 0;`

`}`

You can also download the source code for this problem here and compile it on your local machine.

Further Analysis