Why does this take so long to execute?

Mar 17, 2013 at 1:19am
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#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.
Mar 17, 2013 at 1:47am
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.
Mar 17, 2013 at 2:56am
closed account (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
Mar 17, 2013 at 3:20am
Oh... does that make it so that each time only one number gets added to it instead of every single previous number?
Mar 17, 2013 at 3:35am
@eagleman: O(n^3) is too big.
Mar 17, 2013 at 5:35am
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:

1
2
3
4
5
6
7
8
9
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:

1
2
3
4
5
6
7
8
9
10
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.]
Last edited on Mar 17, 2013 at 5:49am
Topic archived. No new replies allowed.