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.:
8=2^3
12=2^2*3^1

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…

2 Likes

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!

8 Likes

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;
}
lpfact[i]=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;
if(N==lpfact[N])
{ printf("%d^1\n",N);
return;
}
else
{ a=N; e=0;
while(N>1)
{ p=lpfact[N];
if(a%p==0)
{ a/=p;
e++;
}
else
{ N=a;
printf("%d^%d\n",p,e);
e=0;
}
}
printf("\n");

}

@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
//