CODEWITHSUNDEEP
c++
Bob John
Bob John

Reputation: 3888

#12 Project Euler: Find the first triangle number with over 500 divisors

So I tried working out a solution to this problem, but my program is acting very strange.

#include <iostream>
using namespace std;

int triangle_numbers(int n, int meh = 0)
{
    int count = 0;

    //calculate how many divisors there are for meh
    for(int i = 1; i <= meh; i++)
        if(meh%i == 0)
            count++;

    //if the number of divisors for meh is over 500, return meh
    if(count > 500)
        return meh;

    //recursive call to increment n by 1 and set meh to the next triangle number
    triangle_numbers(n+1, meh += n);
}

int main()
{
    int cc = triangle_numbers(1);
    cout << cc << endl;
}

If I output meh and count individually I get accurate results, so I'm not sure why my program is giving me the same number (4246934) even if I do, say, if(count > 10). I have a feeling it may have to do with my recursive call, but everything I've tried so far hasn't worked. Any help?

Upvotes: 0

Views: 584

Answers (1)

Jon
Jon

Reputation: 437634

You are missing a final return statement necessary to complete the recursion (doesn't the compiler warn that triangle_numbers does not actually return something in all cases?).

Once the final value of meh has been computed, you need to have

return triangle_numbers(n+1, meh += n);

so that meh can be returned all the way back up the call stack and finally to main.

The number you are seeing now is probably a value left over on the stack after the recursion does end.

Side note: a classic optimization in this algorithm is to have i iterate up to meh / 2 but no further. Obviously numbers greater than half of meh cannot evenly divide it so they can be skipped.

Upvotes: 3

Related Questions