Project Euler #3 In C++ 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 &lt;list&gt;
#include &lt;algorithm&gt;
#include &lt;iostream&gt;

template &lt;class T&gt;
std::list&lt;T&gt; TrialFactorization(T n) {
    std::list&lt;T&gt; base_factors;
    if(n == 1 || n == 2)
        base_factors.push_back(n);
    for(T p = 2; p &lt; n; ++p) {
        while(n % p == 0) {
            n /= p;    // &lt;~~ 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&lt;my_type&gt; my_base_factors = TrialFactorization&lt;my_type&gt;(my_int);
    // std::cout &lt;&lt; *std::max_element(my_base_factors.begin(), my_base_factors.end());
    // Exploit sorted.
    std::cout &lt;&lt; (* --my_base_factors.end());
}
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).