riningan's blog

Prime Factorization In log(n) After Sieve
By riningan, 8 years ago, In English

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.

 
 
 
 
  • Vote: I like it
  • +8
  • Vote: I do not like it

Comments Comments (56)
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

[:||||||:] David Gries, Jayadev Misra. A Linear Sieve Algorithm for Finding Prime Numbers, 1978. read this (in Russian)

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

So many minuses, why? It's very useful trick and I don't think that everyone knows it.

→ Reply
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Really nice trick! Thanks for sharing.

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yeah right, thank for sharing this !!

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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!

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how can we find factorization from sp[]..please explain?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    vector <int> factorize(int k) {
	vector <int> ans;
	while(k>1) {
		ans.push_back(sp[k]);
		k/=sp[k];
	}
	return ans;
}
    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How large can MAX be?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Any problems to solve with this technique ???

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

hey smallest prime factor for 567 is 3 but you program is outputing 7...plz correct it

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sorry but you are mistaken.It is giving 3 as the output.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      actually i am converting it in java code may be due to i am getting this...if u can convert this in java then it would be very helpful for me and for othes..plz do it soon

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it -6 Vote: I do not like it

      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;
         }
       }
    }
}
      → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This is really nice! Thanks for sharing.

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I don't know why I m getting segmentation fault for the spf() function... http://codepad.org/cKUBvEJ2

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I am not able to understand that why is it log(n) ???

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Amazing... thanks :)

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

      what is the overall complexity of the Sieve() function mentioned above

      → Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I think this can be done without extra space :)

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please share how to do it?

    → Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Nice trick.Helped me to optimise my code. Thanks :)

→ Reply
»
4 years ago, # |
  Vote: I like it -6 Vote: I do not like it

Code for Linear Sieve Algorithm Already available on GeeksforGeeks here http://www.geeksforgeeks.org/sieve-eratosthenes-0n-time-complexity/

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to find largest prime factor when Number is greater than 10^9 and what is the largest prime factor of 10^16?

→ Reply
»
4 years ago, # |
  Vote: I like it -35 Vote: I do not like it

why this code is not working ? and if we ant to compute for long range up to 10 ^ 12 than what ?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

realy good idea

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

thanks nice trick...

→ Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I have kind of more simplified code.. without that array v We don't need that bool array to check every time if we need to update it or not we can do it with just one array

https://www.ideone.com/rJfFNC

→ Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Alas you perform in yor code a lot of unnecessary work. Inner cicle should be executed only for prime values and not for any i.

    → Reply
    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thanks for pointing out.. corrected it! https://www.ideone.com/mJ4xSS

      → Reply
      • »
        »
        »
        »
        14 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Good! But what if $$$n$$$ is 49 (I hint on i*i<n) and not 50? Can we merge two cicles in one? Can we separate the case with i=2 and then do not only i++ and j=i*i but also i+=2 and j+=2*i? What if i becomes too large and i*i exceeds MAX_INT? Can we use linear sieve for better performance? Sorry for all this questions...

        → Reply
        • »
          »
          »
          »
          »
          14 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          1. whenever we are asked to find the smallest prime for first n numbers then we would define N as something safe.. like n+10
          2. separating the case for even numbers .I don't understand why every where I see this is done?... how much computational overhead are we reducing .. is it even significant?
          3. we can store the numbers in long long
          → Reply
        • »
          »
          »
          »
          »
          14 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          here is the code after keeping in mind the things you said.. https://www.ideone.com/obqH09

          would linear sieve be better than this?

          → Reply
          • »
            »
            »
            »
            »
            »
            14 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            You mean that n is excluded from the sieve. Ok. I mean it this way (here n is included into the sieve). As you can see the linear sieve is a bit faster. Nevertheless at the last end we get a good optimized easy-coded sieve :)

            → Reply
»
6 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Hi, Can we modify the same technique further? Like I try so this is right or wrong. Because in my code outer loop only runs sqrt(n) instead of O(n). So total time complexity would be sqrt(n)*log(n). Let me know if I am doing something wrong.

ll  Max=1e7+1;
vi SmallestPrimeFactory(Max,-1);


void SmallPrimeFactor(){
    SmallestPrimeFactory[0]=0;SmallestPrimeFactory[1]=0;
    for(int i=2;i<Max;i+=2)       SmallestPrimeFactory[i]=2;
    for(int i=3;i*i<=Max;i+=2){
        if(SmallestPrimeFactory[i]==-1){
            SmallestPrimeFactory[i]=i;
            for(int j=i;j*i<Max;j+=2){
                if(SmallestPrimeFactory[j*i]==-1)
                      SmallestPrimeFactory[j*i]=i;
            }                 
        }
    }
}
→ Reply