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 &lt;= 10^7).

I am using an array of vectors of pairs.  The format for 10 is as follows:

PF[10][0].first = 2 // Base
PF[10][0].second = 1 // Exp
PF[10][1].first = 5
PF[10][1].second = 1


My approach is working fine but it is too slow.  For M=10^7 it took 36.841 sec to compute PF of all numbers &lt;=M on my system.

Questions


Which is the best approach for this question?
For my approach what other optimizations can i do?


My code

#include &lt;iostream&gt;
#include &lt;fstream&gt;
#include &lt;vector&gt;
#include &lt;utility&gt;
#include "math.h"
#include "stdio.h"
using namespace std;

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

vector&lt;pair &lt;int,unsigned char&gt; &gt; PF[Max];

void prep()
{
    //Calculation of Prime Numbers
    for(int i=1;i&lt;lim;prime[i++]=1);
    for(int i=2;i*i&lt;lim;i++)
        if(prime[i])
            for(int j=i+i;j&lt;lim;prime[j]=0,j+=i);

    for(int i=2;i&lt;Max;i++) {
        int num=i;
        unsigned char pq=0;
        //Check for powers of 2
        while(num%2==0)  {
            pq++;
            num=num/2;
        } 
        if(pq&gt;0)
            PF[i].push_back( make_pair(2,pq) );
        int pan=num;
        //Loop for all primes j such that j*j&lt;num
        for(int j=3;j*j&lt;=num;j+=2) {
            if(prime[j]) {
                pq=0;
                while(num%j==0) {
                    pq++;
                    num=num/j;
                } 
                if(pq&gt;0)
                    PF[i].push_back( make_pair(j,pq) );
            }
        }
        if(num&gt;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 &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