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 &lt;iostream&gt;
#include &lt;math.h&gt;

using namespace std;

int getDivisorCount(unsigned int number)
{
    unsigned int count = 0;
    unsigned int sqrt_ = sqrt(number);
    for(unsigned int i = 1; i &lt;= sqrt_; i++)
    {
        if((number % i) == 0)
            count+=2;
    }
    if (sqrt_ * sqrt_ == number)
    {
        count--;
    }
    return count;
}

int main()
{
    unsigned int number = 0;
    for (unsigned int i = 1; ; i++)
    {
        number+=i;
        if(getDivisorCount(number)&gt;500)
            break;
    }
    cout &lt;&lt; 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 &lt;= 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)&gt;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) &lt;= 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) &lt;= 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 &lt;&lt; number;


with 

std::cout &lt;&lt; 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)\$.