6
\$\begingroup\$

The question for reference:

The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143?
answer: 6857

I'm looking for general feedback as to style and particularly usage of the STL. Efficiency is a concern but a simple link to a better algorithm will suffice.

#include <list>
#include <algorithm>
#include <iostream>

template <class T>
std::list<T> TrialFactorization(T n) {
    std::list<T> base_factors;
    if(n == 1 || n == 2)
        base_factors.push_back(n);
    for(T p = 2; p < n; ++p) {
        while(n % p == 0) {
            n /= p;    // <~~ Shortens outer for-loop.
            base_factors.push_back(p);
        }
    }
    if(n != 1)
        base_factors.push_back(n);
    return base_factors;
}

int main() {
    typedef long long my_type;
    my_type my_int = 600851475143LL;
    std::list<my_type> my_base_factors = TrialFactorization<my_type>(my_int);
    // std::cout << *std::max_element(my_base_factors.begin(), my_base_factors.end());
    // Exploit sorted.
    std::cout << (* --my_base_factors.end());
}
\$\endgroup\$
  • \$\begingroup\$ could have used my_base_factors.back() instead of *(--my_base_factors.end()) \$\endgroup\$ – cheezsteak Dec 11 '14 at 19:29
5
\$\begingroup\$

You can improve the performance of the inner divisibility test by using std::div to do the division and modulo operations in one step. The following should work:

    for (;;) {
        auto r = std::div(n, p);
        if (r.rem != 0) {
            break;
        }
        n = r.quot;
        base_factors.push_back(p);
    }

The return value of std::div is a type such as std::lldiv_t (the exact return type ultimately depends on the template type parameter T).

\$\endgroup\$
  • \$\begingroup\$ For templates, auto is the way to go to get the actual return type of std::div whatever the integer type. \$\endgroup\$ – Morwenn Dec 17 '14 at 18:44
  • \$\begingroup\$ @Morwenn: Of course, thanks. I've updated my answer. \$\endgroup\$ – Greg Hewgill Dec 17 '14 at 19:10
4
\$\begingroup\$

An optimisation

You are getting the prime factorisation testing divisibility of various numbers.

You know that if you find a divisors p that way, it has to be prime but it will also be such that p * p <= n (n being the "current" version of the variable, not the one passed as an argument). Thus, you can stop the loop much earlier : for(T p = 2; p*p <= n; ++p).

A tiny bug

Because this has no impact on your code, you have no particular way to identify this but the prime decomposition of 2 gives 2*2 which is obviously wrong.

It could be interesting to add (in the debug version) some check that the product of the factors gives the original number.

\$\endgroup\$
0
\$\begingroup\$

Overall looks good.

You may speed TrialFactorization up about twice (doesn't touch asymptotics though) by special casing p == 2. Then in the loop you can increment p by 2 instead of 1.

\$\endgroup\$
  • \$\begingroup\$ Like this while(p == 2 || n % p == 0)? \$\endgroup\$ – cheezsteak Dec 11 '14 at 18:05
  • \$\begingroup\$ @cheezsteak: while (n % 2 == 0) { n /= 2; } followed by for (p = 3; p < n; p += 2) { ... } \$\endgroup\$ – vnp Dec 11 '14 at 18:22
0
\$\begingroup\$

Instead of declaring the type outright, you can just let the compiler do the work for you.

int main() {
    auto my_int = 600851475143LL;
    auto my_base_factors = TrialFactorization(my_int);
    std::cout << (* --my_base_factors.end()); 
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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