Optimization - Prime Factorizations of Numbers <= 10^7

I am using Trail Division Method with a pre-calculated list of primes to calculate the prime factorization of all numbers less than M (M

• For my approach what other optimizations can i do?

My code

#include 
#include 
#include 
#include 
#include "math.h"
#include "stdio.h"
using namespace std;

const int lim=45000;
const int Max=10000000;
char prime[lim];

vector > PF[Max];

void prep()
{
    //Calculation of Prime Numbers
    for(int i=1;i0)
            PF[i].push_back( make_pair(2,pq) );
        int pan=num;
        //Loop for all primes j such that j*j0)
                    PF[i].push_back( make_pair(j,pq) );
            }
        }
        if(num>1)
            PF[i].push_back( make_pair(num,1) );
    }
}

main()
{
    prep();
}

Timing

My Code

real    0m36.841s
user    0m36.624s
sys     0m0.265s

Igor ostrovsky Code

real    0m41.628s
user    0m41.390s
sys     0m0.265s

I did this a while ago, in the interest of reducing ratios of factorials

#include 
#include 

std::vector > factor_table;
void fill_sieve( int n )
{
    factor_table.resize(n+1);
    for( int i = 1; i (i, 1);
        else
            factor_table[i] = std::pair(2, i>>1);
    }
    for( int j = 3, j2 = 9; j2 (j, i);
                ++i;
                ij += j;
            }
        }
        j2 += (j + 1)  factor( int num )
{
    std::vector 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 takes 5x as long as the factor generation.)

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

Original application:

• http://ideone.com/Weeg6

StackExchange Code Review Q#9052, answer score: 4