### riningan's blog

By riningan, 11 years ago,

We use Eratosthenes sieve for prime factorization, storing the primes in an array. But for that, we need to find the primes less than or equal to sqrt(n) which divide n. There are about n/log(n) primes less than or equal to n. So, the complexity is roughly sqrt(n)/log(sqrt(n))*log(n). But if n is asked to be factorized completely where n is within the Sieve range, then we can factorize n is log(n) complexity. And the trick is fairly small. Observe, that, we don't need to run a whole sqrt(n) loop for finding the prime divisors. Instead, we can even store them when n is in the range, say n<= 10^7. But the tricky part is not to store all the prime divisors of n. Let's see the following simulation. Take n = 60. We want to factorize n. We will store the smallest prime factors only. This does the trick. If n is composite, then it has such a prime factor, otherwise n is a prime and then the n itself is the smallest prime factor. It is obvious, for any even number n, sp(n)=2. Therefore, we only need to store these primes for odd n only. If we denote the smallest prime factor of n by sp(n), for odd 2 <= n <= 30, we get the following list.

sp(2n)=2, sp(3)=3, sp(5)=5, sp(7)=7, sp(9)=3, sp(11)=11, sp(13)=13, sp(15)=3, sp(17)=17, sp(19)=19, sp(21)=3, sp(23)=23, sp(25)=5, sp(27)=3, sp(29)=29.

Then the factorization is very simple. The optimization is needed only once, when the Sieve() function runs.

bool v[MAX];
int len, sp[MAX];

void Sieve(){
for (int i = 2; i < MAX; i += 2)	sp[i] = 2;//even numbers have smallest prime factor 2
for (lli i = 3; i < MAX; i += 2){
if (!v[i]){
sp[i] = i;
for (lli j = i; (j*i) < MAX; j += 2){
if (!v[j*i])	v[j*i] = true, sp[j*i] = i;
}
}
}
}

int main(){
Sieve();
for (int i = 0; i < 50; i++)	cout << sp[i] << endl;

return 0;
}



Now, notice the difference between the usual prime factorization and this one! The only problem is, you can't use this for n large enough in int range. Still, it seems nice to me and pleasured me when I first found this.

• +8

| Write comment?
 » 11 years ago, # |   +1 [:||||||:] David Gries, Jayadev Misra. A Linear Sieve Algorithm for Finding Prime Numbers, 1978. read this (in Russian)
•  » » 11 years ago, # ^ |   0 hmm.
 » 11 years ago, # |   0 So many minuses, why? It's very useful trick and I don't think that everyone knows it.
 » 11 years ago, # |   +5 Really nice trick! Thanks for sharing.
 » 11 years ago, # | ← Rev. 2 →   0 It's better to precalculate not only smallest prime number, but also quotient cp[i] = i / lp[i], to do not unnecessary and TOO SLOW operations of division, especially in case of big number of queries.
•  » » 11 years ago, # ^ |   0 I think that it is not important. Original source is easy to read and easy to understand. Also, you have to perform divide operations log(n) times only. It seems not too big.
 » 11 years ago, # |   0 Dude, your tricks is really cool but I think there is some problem in your sample code. Your Sieve() function doesn't store the smallest prime factors properly. For 45, the smallest prime factor should be 3 where according to your sample code it stores 5!
•  » » 11 years ago, # ^ |   0 that's because I forgot to check first if a number already has a smallest prime divisor. Now it is correct. Thanks for pointing the mistake out.
 » 9 years ago, # |   0 how can we find factorization from sp[]..please explain?
•  » » 9 years ago, # ^ |   0 vector factorize(int k) { vector ans; while(k>1) { ans.push_back(sp[k]); k/=sp[k]; } return ans; } 
 » 9 years ago, # |   0 How large can MAX be?
•  » » 9 years ago, # ^ |   0 10^7
•  » » » 9 years ago, # ^ |   0 Hi Dushyant, If the limit is 10^7 then why this code is not working. I have commented out the rest part which is not concerned....
•  » » » » 9 years ago, # ^ |   0 Signed integer overflow — http://ideone.com/FXLHXO :)
•  » » » » 7 years ago, # ^ |   0 The reason is integer overflow. To overcome from it, before starting the 2nd loop of j, add this condition:if(i>sqrt(N)) continue;
•  » » » 8 years ago, # ^ |   0 what should i do for nos of 10^9 range?
•  » » » » 8 years ago, # ^ |   0 It can be Pollard's "Ro" algorithm or smth like that.
•  » » » » » 8 years ago, # ^ |   0 I got Pollard's "Ro" algorithm.really nice one.thank u @fekete
•  » » » » » » 8 years ago, # ^ |   0 Is it a sarcasm?
 » 9 years ago, # |   0 Any problems to solve with this technique ???
•  » » 9 years ago, # ^ |   0
•  » » 9 years ago, # ^ | ← Rev. 3 →   0 Medium FactorizationOne moreSimple Sum
•  » » 9 years ago, # ^ |   0
 » 9 years ago, # |   0 hey smallest prime factor for 567 is 3 but you program is outputing 7...plz correct it
•  » » 9 years ago, # ^ |   0 Sorry but you are mistaken.It is giving 3 as the output.
•  » » » 9 years ago, # ^ | ← Rev. 2 →   -6 Whats Wrong With this logic every time exception was occuring or it is Same as ABove logic but not Working for java static void Sieve() { for (int i = 2; i < MAX; i += 2) sp[i] = 2;// even numbers have smallest prime factor 2 for (int i = 3; i < MAX; i += 2) { if (!v[i]) { sp[i] = i; for (int j = i; (j * i) < MAX; j+=2) { if (!v[j * i]) v[j * i] = true; sp[j * i] = i; } } } } 
•  » » » » 9 years ago, # ^ |   0 if (!v[j*i]) v[j*i] = true, sp[j*i] = i;
 » 9 years ago, # |   0 This is really nice! Thanks for sharing.
 » 8 years ago, # |   0 I am not able to understand that why is it log(n) ???
•  » » 8 years ago, # ^ |   +6 Consider the prime factorization n = p1 * p2 * ... * pk, where p1, p2, ... pk are the prime factors. n has at most k = log(n) prime factors.To understand this think of how you can maximize the number of prime factors. You'll get the most number of prime factors for p1 = p2 = ... = pk = 2. So we have n = 2^k. Solving for k yields k = log(n).
•  » » » 8 years ago, # ^ |   +3 Amazing... thanks :)
 » 8 years ago, # |   +3 I think this can be done without extra space :)
 » 8 years ago, # |   +5 Nice trick.Helped me to optimise my code. Thanks :)
 » 7 years ago, # |   -35 why this code is not working ? and if we ant to compute for long range up to 10 ^ 12 than what ?
•  » » 7 years ago, # ^ |   0 This code only works for MAX <= 1e7
 » 5 years ago, # |   0 thanks nice trick...