-4

So i came up with this solution to ProjectEuler problem 29 (http://projecteuler.net/problem=29)

The answer is right. I would expect this code to run pretty fast but it runs extremely slowly. I have no idea why.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef vector<pair<int,int>> factorized_int; // pairs of base, exponent

factorized_int primeFactors(int n) {
        int primeFactors[100] = {0};
        for (int i=2; i <= n; i++) {
                if (n%i == 0) {
                        primeFactors[i]++;
                        n /= i;
                        i--;
                }
        }

        vector<pair<int,int>> retValue;
        for (int i=2; i<100; i++) {
                if (primeFactors[i] != 0) {
                        retValue.push_back(pair<int,int>(i,primeFactors[i]));
                }
        }

        return retValue;
}

factorized_int pow(factorized_int n, int exponent) {
        factorized_int retValue = factorized_int(n);
        for (size_t i = 0; i<retValue.size(); i++) {
                retValue[i].second *= exponent;
        }
        return retValue;
}

int main() {

        vector<factorized_int> list;

        for (int a=2; a <= 100; a++) {
                factorized_int factorized_a = primeFactors(a);
                cout<<a<<endl;
                for (int b=2; b <= 100; b++) {
                        factorized_int number = pow(factorized_a,b);

                        if (find(list.begin(), list.end(), number) == list.end()) {
                                list.push_back(number);
                        }
                }
        }


        cout<<list.size();
        getchar();
        return 0;
}

Any ideas?

Edit: Most of the answers I am getting are in terms of the algorithmic complexity of the algorithm. Notice that n is pretty low (100) and also:

int main() {

            vector<factorized_int> list;

            for (int a=2; a <= 100; a++) {
                    factorized_int factorized_a = primeFactors(a);
                    cout<<a<<endl;
                    for (int b=2; b <= 100; b++) {
                            /*factorized_int number = pow(factorized_a,b);

                            if (find(list.begin(), list.end(), number) == list.end()) {
                                    list.push_back(number);
                            }*/
                    }
            }


            cout<<list.size();
            getchar();
            return 0;
    }

runs almost instantely. This make me think that the problem is with the constant in the O(n) of the pow function. I think the problem is realted to the various copies of std::vector in the call to pow(factorized_int,int) How could I check and optimize that?

Note: In my PC, the commented version runs in less than 0.1 seconds, and the first one takes more than 30 seconds

13
  • 5
    This question appears to be off-topic because it is about code review, and belongs on codereview.stackexchange.com.
    – Carl Norum
    Jul 17, 2013 at 20:43
  • 2
    In terms of Big O notation calculate the costs. You'll see why it's exponentially slower due to the nested loops, and the recursive nature of the beast. Jul 17, 2013 at 20:44
  • 1
    @Trollkemada I suggest that you read a little more about prime number algorithms. Jul 17, 2013 at 20:44
  • 3
    the solution on project euler is almost never to brute force it Jul 17, 2013 at 20:46
  • 2
    you should use a set instead of a vector if you want unique items. The syntax then becomes set.insert(number) and you can drop the if ( find(...) ) condition. Alternatively: just push all values into the vector, then at the end, just sort it and erase duplicates. This may be faster
    – stefan
    Jul 17, 2013 at 20:57

1 Answer 1

7

You aren't clear on what 'fast' or 'slow', is, but:

int main() {
        vector<factorized_int> list;

        for (int a=2; a <= 100; a++) { //O(a)
                factorized_int factorized_a = primeFactors(a); //O(2a)
                cout<<a<<endl;
                for (int b=2; b <= 100; b++) {  //O(b)
                        factorized_int number = pow(factorized_a,b);//O(2b)

                        if (find(list.begin(), list.end(), number) == list.end()) {
                                list.push_back(number);
                        }
                }//total of O(b*2b) => O(b^2)
        }//total of O(a * (2a + b^2)) => O(n^3)


        cout<<list.size();
        getchar();
        return 0;
}

The annotations indicates, roughly, the algorithmic complexity of your function calls. You have an O(n^3), which is pretty slow.

9
  • And with the amount of the data that this person has to handle, this is REALLY bad. Good explanation
    – taylorc93
    Jul 17, 2013 at 20:45
  • absolutely 100% right. +1. In terms of Big O, the nested for loops is costing you a lot. Jul 17, 2013 at 20:46
  • 2
    @stefan It is idiomatic to use n to roll up a diverse set of input variables. Because a and b aren't directly comparable, but are roughly on the same order, it's fine to use n to include both for a rough analysis - which this is. Jul 17, 2013 at 20:47
  • @stefan I did include what n meant in the answer, but good catch on the math. Jul 17, 2013 at 20:51
  • 1
    @Trollkemada Given that it's within two orders of magnitude, I'm still chalking this up to algorithmic complexity. You're correct that copying might take much longer, so your O(b) factor is larger than your O(a) factor, but you're still doing this in a slow manner. Jul 17, 2013 at 21:00

Not the answer you're looking for? Browse other questions tagged or ask your own question.