Prime factorization of large numbers

I have a query kind of a problem in which no of range 10^7 needed to be prime factorized, so in pre processing I require that all the no less than 10^7 are in the form of prime factors i.e.:

I used sieve of Erastothenes to find the prime no but can’t figure out how to factorize all the no in the form of their powers of prime factors…
Pls help…


It can be done by a trick. You can precompute the lowest prime factors of every number i<=10^7. Observe that every even number has smallest prime factor 2. For other numbers seive can be implemented which will be faster than usual.

Say this precomputed array be lpfact[].

Now you can divide the input number by lpfact[n] till it divides it clearly and keep track of the power. for example; if the number is 12; lpfact[12], after dividing two times, the number becomes 3; dividing by lpfact[3], it becomes 1.

So, you get the answer as 2^2*3^1.

You may notice that each query takes time not more than log(n).

Hope it helps!


thanks a lot buddy… but there is a problem in it …
the logic is failing for large inputs and giving wrong answers :frowning:

static final int MAX = 10000009;
static boolean v[] = new boolean[MAX + 10];
static int sp[] = new int[MAX + 10];
static boolean prime[]= new boolean[MAX+10];

static void sieve2() {
Arrays.fill(prime, true);prime[0]=false;prime[1]=false;sp[1]=1;v[2] = true;for (int i = 2; i < MAX; i += 2) {sp[i] = 2;v[i] = true;prime[i]=false;}for (int i = 3; i < MAX; i += 2) {if (!v[i]) {sp[i]=i;if ((i * i) < MAX){for (int j = 1; j * i < MAX; j++) {if (!v[i * j]) {sp[j * i] = i;[j * i] = true;prime[j*i]=false;}}}}}}
sp[] stores lowest prime factor of each numberprime[i] is true if i is prime else false

Learned something new today, nice :slight_smile:

@jain_mj I’ve tested it. It should not fail, if it does, your implementation has some problem.
Find out where you are going wrong.

yess, it never fails… i used it too in some questions …!

@xariniov9 @va1ts7_100 pls help me in this solution :
This solution works for small no but fails for large no… pls help :thanks in advance:

(I’m posting it in two parts as comment length is restricted)

@xariniov9 @va1ts7_100 pls help me in this solution :
int lpfact[10000001];
ll _sieve_size=10000001; //ll is defined as typedef long long ll;
bool <10000010> bs;

void sieve(ll upperbound) {
ll _sieve_size = upperbound + 1;

bs.reset(); bs.flip();

bs.set(0, false); bs.set(1, false);

lpfact[0]=0; lpfact[1]=1;

for (ll i = 2; i <= _sieve_size; i++)
{ if (bs.test(i)) {
// cross out multiples of i starting from i * i!
for (ll j = i * i; j <= _sieve_size; j += i)
{ bs.set(j, false);
// also add this vector containing list of primes
if(!lpfact[j]) lpfact[j]=i;

@xariniov9 @va1ts7_100 pls help me in this solution : This solution works for small no but fails for large no… pls help :thanks in advance:

void factorize(int N)
{ int a,e;
{ printf("%d^1\n",N);
{ a=N; e=0;
{ p=lpfact[N];
{ a/=p;
{ N=a;


@jain_mj open this question, I’ll paste the code as another answer.
Or I can provide the ideone link as a comment to the question. :slight_smile:

As one of my answer got many comments, I’m pasting the link to code here. @jain_mj

1 Like