Project Euler Problem 12 - C++

Question

I'm working on problem 12 regarding the first triangle number with 500 divisors. I tried to brute force the solution. I get 300 divisors in about 35 seconds and can't get 400 within 10 minutes. I'm going to alter my solution to use the prime factor method but I've seen now that people are still getting this solution with brute force in under a minute.

Can you please critique my code and tell me if I'm missing something that is making this horribly inefficient?

unsigned long long TriangleNumberDivisors(int divisorTarget)
{
     unsigned long long triangleNum=1;
         unsigned long long currentNum=2;
     int numOfDivisors=0;


     numOfDivisors=NumOfDivisors(triangleNum);
     while(numOfDivisors<divisorTarget)
     {
         triangleNum+=currentNum;
         currentNum++;
         numOfDivisors=NumOfDivisors(triangleNum);
     }

     return triangleNum;
}

 int NumOfDivisors(unsigned long long dividend)
{
    int numDivisors=0;
    set<unsigned long long> divisors;
    set<unsigned long long>::iterator it;

    for(unsigned long long index=1; index<=dividend/2; index++)
    {
        if(dividend%index==0)
        {
            divisors.insert(index);
            numDivisors++;
            it=divisors.find(dividend/index);
            if(it==divisors.end())
            {
                divisors.insert(dividend/index);
                numDivisors++;
            }
              /*for some reason not checking for dups above and 
just checking for how many items are in the set at the end is slower
             for(it=divisors.begin();it!=divisors.end();it++)
             {
                   numDivisors++;
             }
                  */
        }
    }

    return numDivisors;
}

int main()
{
    cout<<TriangleNumberDivisors(500)<<endl;

    return 0;
}

Update: Got it now, thanks. Changed to just check up to square root of the number, and did an additional check to see if it was a perfect square. This allowed me to remove the set entirely as well. 500 divisors ran in 12 seconds.

Answer 1

You currently check for divisors up to dividend/2. You can reduce this to sqrt(dividend), which is asymptotically faster. A special case may be needed if dividend is square.

My C++ code for problem 12 (which does essentially the same as yours, but uses this lower limit, and also just counts divisors rather than storing them in the set) takes about 1 second

Answer 2

for(unsigned long long index=1; index<=dividend/2; index++)

I see you've tried to optimize this by restricting your loop to dividend/2, instead of iterating all the way to dividend. Limiting yourself to sqrt(dividend) would be better (in the sense that you're checking fewer divisors).

Plus, if you limit yourself by the square root of dividend, you don't have to check for duplicate divisors. That will only happen for square numbers, so just check if index==dividend/index, to avoid a duplicate insert.

Answer 3

I am not sure why you need the divisors, a set type variable, in the NumOfDivisors method. Why counting numDivisors (with index upto sqrt( dividend )) is not sufficient? (set is implemented as a balanced binary search tree, it is slowing down the method. ). Moreover, it seems that you are invoking divisors.insert( .. ) twice.

Answer 4

Seems like you could gain some performance if you cached the number of divisors for a particular number as you went along.