Optimization - Prime Factorizations of Numbers <= 10^7
I did this a while ago, in the interest of reducing ratios of factorials

#include &lt;utility&gt;
#include &lt;vector&gt;

std::vector&lt; std::pair&lt;int, int&gt; &gt; factor_table;
void fill_sieve( int n )
{
    factor_table.resize(n+1);
    for( int i = 1; i &lt;= n; ++i ) {
        if (i &amp; 1)
            factor_table[i] = std::pair&lt;int, int&gt;(i, 1);
        else
            factor_table[i] = std::pair&lt;int, int&gt;(2, i&gt;&gt;1);
    }
    for( int j = 3, j2 = 9; j2 &lt;= n; ) {
        if (factor_table[j].second == 1) {
            int i = j;
            int ij = j2;
            while (ij &lt;= n) {
                factor_table[ij] = std::pair&lt;int, int&gt;(j, i);
                ++i;
                ij += j;
            }
        }
        j2 += (j + 1) &lt;&lt; 2;
        j += 2;
    }
}

std::vector&lt;int&gt; factor( int num )
{
    std::vector&lt;int&gt; factors;
    factors.reserve(30);
    do {
        factors.push_back(factor_table[num].first);
        num = factor_table[num].second;
    } while (num != 1);
    return factors;
}


I believe it will be much faster than yours, because I was able to avoid ever using division (/ and %).  As a matter of fact, I don't use any multiplies either.

(It's about 6x faster with g++ than the code in the question, and the actual factor generation part is marginally faster, about 10%, than lol4t0's.  Returning factors in a std::vector&lt;int&gt; takes 5x as long as the factor generation.)

Test program: http://ideone.com/pt9nu

Original application:


http://ideone.com/Weeg6