What is prime factorization?
Example 1: What are the prime factors of 14 ?
It is best to start working from the smallest prime number, which is 2, so let's check:
14 ÷ 2 = 7
Yes, it divided exactly by 2. We have taken the first step!
And 7 is a prime number, so we have the answer:
14 = 2 × 7
As you can see, every factor is a prime number, so the answer must be right.
Note: 14 = 2 × 7 can also be written using exponents as 14 = 21 × 71
Example 2: What is the prime factorization of 147 ?
Can we divide 147 exactly by 2?
147 ÷ 2 = 73½
No it can't. The answer should be a whole number, and 73½ is not.
Let's try the next prime number, 3:
147 ÷ 3 = 49
That worked, now we try factoring 49.
Can we divide 49 exactly by 3?
49 ÷ 3 = 16.33
No it can't. The answer should be a whole number, and 16.33 is not.
Let's try the next prime number, 5:
The next prime, 5, does not work for same reason as 3. But 7 does, so we get:
49 ÷ 7 = 7
And that is as far as we need to go, because all the factors are prime numbers.
147 = 3 × 7 × 7 (or 147 = 31 × 72 using exponents)
1. Naive Approach (Brute Force):
As you may have predicted this is a brute force approach so we will be checking for every possible case.
Basically, we will be doing same process as explained above i.e. we will start checking from smallest prime number (i.e. 2) and if the number is completely divisible by it then we will be continuing the same process for next prime numbers.
Below is the implementation of naïve approach:
Time Complexity: O(n)
2. Optimized Approach – O( sqrt(n) ):
As learned from previous article if you want to optimize any approach try to figure out some observations from it.
Observation:
If ‘N’ is a composite number then there is at least 1 prime divisor of ‘N’
below sqrt(N).
Let’s take an example for understanding this fact:
E.g. 6 = 2 * 3, Now here we can see that sqrt(6) = 2.45(approx.) and we
have 2 in prime factorization of 6 i.e. 2 is below sqrt(6) this proves our
fact.
This fact can be understood with a simple example consider that a number
‘N’ has two prime factors (say ‘p’ and ‘q’) which is greater than sqrt(N)
then we will have p * q > sqrt(N) * sqrt(N) which is a contradiction
hence our observation is correct.
voila !! we optimized our naïve approach once again.
Let’s take an example for understanding this fact also:
E.g. N = 6, p = 3, q = 3 (I know that this is not possible, but assume it
for understanding our contradiction)
here we have sqrt(6) = 2.45 (approx.) and we have ‘p’ and ‘q’ greater than
sqrt(6) now according to mathematics p * q = N, But in our case p * q = 3 *
3 = 9 > 6
Hence, we can conclude here our assumption is wrong and this proves our
fact.
i.e. If ‘N’ is a composite number then there is at least 1 prime divisor of
‘N’ below sqrt(N).
Below is the implementation of optimized approach:
Time Complexity: O( sqrt(n) )
3. Prime factorization using sieve ( O(logn) ):
Pre-requisite: If you have not read our previous article on sieve of
eratosthenes the we highly recommend you to
click here
and read it as we will be using logic of sieve to find prime factors as
we want to make this article understand to you very clearly
😊
.
a. In the sieve algorithm for prime factorization, we start with 2 and we mark all proper multiples of 2 of the form 2k where k>1 as composite.
b. We then go the next unmarked number and simulate the same process.
c. The idea is that, when we get a prime number p, and mark all the multiples of that prime kp as composite (where k>1), we can say that p is a prime factor of that multiple kp.
d. This way we can store all the prime factors of a number in an array.
e. We’ve computed all the prime factors. But we still don’t know how many times the prime factor exists.
f. So, for each prime factor Pi, we need to calculate its power i.
g. For this we will calculate the power of each prime factors. (Note: We can even pre-compute this for better optimization).
Below is the implementation of prime factorization using sieve:
Pre-processing Time Complexity : O( NLog(LogN) )
Answering Query : O(LogN)
Extra Space : O(N)
Note : The pre-processing time is more for this algorithm but this makes us answer query in logarithmic time, and this is why sieve is much important in number theory for finding prime factorization of given number.
So that’s it for this article we will be coming up with our next article on further topics of number theory very soon till then keep learning, keep coding, keep reading and keep improving !!
Happy Coding 😊
By Programmers Army