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