Project Euler #3 In C++

Question

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());
}

• cheezsteak: could have used my_base_factors.back() instead of *(--my_base_factors.end())

Answer 1

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).

• Morwenn: For templates, auto is the way to go to get the actual return type of std::div whatever the integer type.
• Greg Hewgill: @Morwenn: Of course, thanks. I've updated my answer.

Answer 2

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.

Answer 3

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.

• cheezsteak: Like this while(p == 2 || n % p == 0)?
• vnp: @cheezsteak: while (n % 2 == 0) { n /= 2; } followed by for (p = 3; p < n; p += 2) { ... }

Answer 4

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()); 
}