Why does this take so long to execute?

[eagleman]

#include <iostream>
#include <vector>
using namespace std;
int factors (int a){
    int b = 0;
    for (int f = 1; f <= a; f++)
    {

        if (a % f == 0)
         b++;
    }

return (b);
}
int main()
{
  vector<int>v;
   int x, g;
    for (int i = 1;;i++)
    {
        v.push_back(i);
        for (g = 0, x = 0; g < i; g++)
        {
            x+= v[g];

        }

        if (factors(x) > 500)
        {
           cout << x;
           return 0;
        }
    }
    return 0;
}

It is only 35 lines, but it is taking at least 15 minutes to run. I have a fast computer- right now the cpu is running at 3.5 ghz. The program should be able to run in less than 1 minute.

[firedraco]

The program should be able to run in less than 1 minute.

Try looking at the for loop in your main function and ask yourself whether your statement is true.

[Dy7SLyTq]

thats not the problem. its the nested one. move the x = 0 to outside all of the loops and then it should work fine

[eagleman]

Oh... does that make it so that each time only one number gets added to it instead of every single previous number?

[ne555]

@eagleman: O(n^3) is too big.

[cire]

DTSCode wrote:

thats not the problem. its the nested one. move the x = 0 to outside all of the loops and then it should work fine

There is, indeed, an issue with the inner loop, but (as usual) DTSCode knows less than he thinks he does. Simply moving x=0 outside of all the loops will cause your code to take just as long to execute and be inaccurate to boot.

As inefficient as the main loop is, it is completely dwarfed by your factors algorithm.

main could be written thusly:

int main()
{
    std::vector<unsigned> v(1, 1) ;

    while ( factors(v.back()) < 500 )
        v.push_back(v.back() + (v.size()+1)) ;  // last number calculated + next term number

    std::cout << v.back() << '\n' ;
}

Of course the vector isn't really needed. You could also write it:

int main()
{
    unsigned term = 1 ;
    unsigned value = 1 ;

    while ( factors(value) < 500 )
        value += ++term ;  // last number calculated + next term number

    std::cout << value << '\n' ;
}

but until you develop a better algorithm for factors, I hope you've got awhile to wait.

[Edit: You might find http://www.wikihow.com/Find-How-Many-Factors-Are-in-a-Number inspiring.]