Project Euler #12 - first triangle number with more than 500 divisors

I tried to solve Project Euler 12 with a first very naive solution by myself. It took nearly 30 minutes to run until it found the solution. Then I made a change in the function getDivisorCount which should have made the run time to about the square root of the original code, about 5 minutes. At least this was my opinion because the complexity should have changed from \$O(n^2)\$ to \$O(n\sqrt n)\$. But it went down to less than a second which surprised me and I could not find a reason.

Here is my code for review, a second time:

#include 
#include 

using namespace std;

int getDivisorCount(unsigned int number)
{
    unsigned int count = 0;
    unsigned int sqrt_ = sqrt(number);
    for(unsigned int i = 1; i 500)
            break;
    }
    cout << number;
    return 0;
}

Note that my first version used the method:

int getDivisorCount(unsigned int number)
{
    unsigned int count = 0;
    for(unsigned int i = 1; i <= number; i++)
    {
        if((number % i) == 0)
            count++;
    }
    return count;
}

Both compiled with g++ -O2.

I'm looking for a fresh code review, but an explanation of why the current version is so much faster would also be appreciated.

Nitpicks

using namespace std;

This can be a bad habit to start. See Why is using namespace std bad practice?

unsigned int sqrt_ = sqrt(number);

I don't like the name sqrt_. Something like sqrt_number would be better in my opinion.

unsigned int number = 0;
for (unsigned int i = 1; ; i++)
{
    number+=i;
    if(getDivisorCount(number)>500)
        break;
}

That's an odd way to write a loop. You are iterating i but never checking it. I would prefer something like

for ( unsigned int number = 1, i = 2; getDivisorCount(number) <= 500; number += i, i++ ) ;

That's rather dense -- it might be easier in a while loop. But at least this has a variable declaration, a loop check, and an increment. Also, it avoids having to break to exit the loop.

unsigned int number = 1;
unsigned int i = 2;
while ( getDivisorCount(number) <= 500 ) {
    number += i;
    i++;
}

Analysis

You refer to your original code as quadratic, but quadratic in what? The outer loop in main runs i times. The inner loop runs number times. What's number in terms of i? The answer is that number is quadratic in i. I.e. \$O(i^2)\$. So we actually run the inner loop in getDivisorCount \$O(i^3)\$ times.

The optimized loop only runs the square root of number times. But we know that the square root of number is about i. So overall, it runs \$O(i^2)\$ times.

So the difference between the two is about i in magnitude. What's i in this case? Well, without giving the exact answer, I'll tell you that it's over 10,000. You can get the exact answer by replacing

cout << number;

with

std::cout << i;

Note that you may have to move the declaration of i outside the loop.

Anyway, that's why your revised code is more than 10,000 times faster than your original code. That's how big i was.

More generally, when going from \$O(n^2)\$ to \$O(n)\$ in an otherwise similar algorithm, you don't take the square root of the time. You divide by n. In this case, i or number is n. This is why \$O(n)\$ is so much better than \$O(n^2)\$.

StackExchange Code Review Q#74982, answer score: 7