Finding the first triangle number with over five hundred divisors

Question

Project Euler 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.

---

The code runs correctly, but I want to know if I can make any improvements to the code.

#include <iostream>
#include <limits>
#include <cmath>
int highlyDivisibleTriangularNum();

int main() {
std::cout <<highlyDivisibleTriangularNum() << std::endl;
return 0;
}

int highlyDivisibleTriangularNum()
{
//The number to be added to all the previous numbers
int i = 1;
//The number that adds all the previous numbers
int overallAdd = 0;
//Max number
int max = std::numeric_limits<int>::max();
for(int counter = 0; counter < max; counter++)
{
    int total = 0;
    int sum = overallAdd + i;
    i++;
    overallAdd = sum;

    int sqrtSum = (int)sqrt(sum);
    for(int c = 1; c <=sqrtSum;c++)
    {
        if(sum%c == 0)
        {
            total += 2;
        }
        if(total > 500)
        {
            return sum;
        }
    }

}
return 0;
}

Answer 1

• Code

  • total += 2 is a bug. In case sum is a perfect square, and c happens to be its root, total shall be incremented by 1.

  • Using floating point (sqrt) in a number theoretical problem is dubious at best.

  • You don't need overallAdd. sum += i; suffices.

  • Naming looks arbitrary. The sum is a triangular number, total is a sum of divisors, so call them appropriately. Single-letter identifiers, like c shall be avoided.

  • Add your operators some breathing space.

  • Inner loop computes the number of divisors. Better factor it into a separate function.

• Algorithm is brute force, which is never good, especially for Project Euler problems. This problem was discussed here many times. See this shameless self-plug for example.

Answer 2

You can get one massive improvement: A triangular number n(n+1) / 2 can be written as (n/2) (n+1) if n is even, and n ((n*1)/2) if n is odd. That’s the product of two co-prime integers, and for co-prime integers a, b the number of divisors of a x b is the product of divisors of each number. Say n = 1,000,000 then you calculate the divisors of two six digit numbers instead of one twelve digit number.

The second massive improvement: you don’t need the number of divisors if you know it’s less than 500. Numbers with no divisors less than n^(1/3) have at most four divisors.

And of course factoring is massively faster than counting divisors.

Answer 3

Put main at the bottom, so you don’t have to forward-declare the functions it calls.

Don’t use endl. It is slow and doesn’t add anything. (Output a \n)

Use const or constexpr where you can. In particular,

constexpr int max = std::numeric_limits<int>::max();

Get used to writing prefix increment. For ints where you don’t use the result it does not matter; but then you have to know which cases are OK and double-check during review rather than always doing it the normal way.

Performance

The modulo operation is exceptionally slow. If you can figure out how to avoid it (such as by keeping track of remainders), you will come out ahead.