Highly Divisible Triangular Number

Problem

Problem Link

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,\dots$

Let us list the factors of the first seven triangle numbers:

$$\begin{array}{c}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\end{array}$$

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?

Solution

CodeCPP fileDownload

#include <iostream>
 
int divisor_count(int n) {
  int ret = 1;
  for (int i = 2; i * i <= n; ++i) {
    int count = 0;
    while (n % i == 0) {
      n /= i;
      count++;
    }
    ret *= (count + 1);
  }
  return n > 1 ? ret * 2 : ret;
}
 
int main(void) {
  int n = 0;
  for (int i = 1;; ++i) {
    n += i;
    if (divisor_count(n) > 500) {
      std::cout << n << std::endl;
      break;
    }
  }
  return 0;
}