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.

• austingae: What do you mean "Using floating point (sqrt) in a number theoretical problem is dubious at best."?
• vnp: @austingae Floating point operations are inherently imprecise, and introduce rounding errors. For large enough argument sqrt(n) may not be equal the true square root. As long as you can avoid them, do so. In this particular case, a condition c * c <= n is preferable.
• JDługosz: @vpn will a double sqrt ever be too small for integers up to 31 bits? I think it’s OK if you add 1 to the result to prevent rounding down wrongly. For some small value, calculating the max once using a sqrt will be faster than squaring on every iteration. (But there are faster ways to generate consecutive squares...)
• maaartinus: @austingae At least in Java, usingsqrt for this is fine, as it's guaranteed to return the closest representable result. No idea, what guarantees offers C++, if any. It actually works even for 64-bit arguments, but of course, caution is advised.
• Kevin: @maaartinus: That's not quite true; in IEEE754 double-precision floating point, the number 9007199254740993.0 is equal to 9007199254740992.0. Both are easily representable as 64-bit integers with 10 or 11 bits to spare (signed/unsigned). "Correctly rounded" means "rounded to the closest floating point number available"; it does not mean that the closest floating point number is actually close enough to give you the right integer. It happens to work out for square root because the input would have to be unrepresentably large to trigger this problem.

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.

• JDługosz: This SE is for code reviews, not for "how do I approach this number theory problem?"
• Luke Hutchison: @JDługosz yes, but an important part of code review is algorithm review and code efficiency review, and these were some really good suggestions.

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.

• austingae: Isn't it good to declare the functions before the main method so I know what methods are available to me? Like if I had like 15 methods, I wouldn't want to scroll down to check the method's name.
• austingae: I find using endl easier to read than \n. Is the performance issue a really big difference that \n is better to use than endl?
• Kevin: @austingae: For a single use, no. But if you use std::endl every time you need a newline, you will have issues. The only difference is that std::endl flushes the stream, which is completely unnecessary in your code (the program is about to terminate, which flushes the stream automatically).
• gnasher729: You have focused on nano-optimisations that will have zero effect on the runtime in this case.
• JDługosz: @austingae easy: define your own end symbol as a stream manipulator or simply as a constant char for \n.