Number Theoretic Algorithms – Factorization
In the following series of posts, I will write about some of the number theoretic algorithms that one encounters in most of competitive programming. These are fundamental algorithms which most computer scientist should know.
In this post I will post an algorithm and a corresponding JAVA code to perform prime factorization of a give number.
The algorithm to perform prime factorization is a very trivial algorithm and mostly encountered by everyone atleast once in their high school.
- Iterate for i from 1 to sqrt(n) - While i|n, divide n by i. Report i as a prime factor of n - After the iteration of i from 1 to sqrt(n), if n is a number greater than 1, report that also as a prime factor
The key observation is that, this algorithm runs in O(square root (n) ).
We are able to iterate only upto sqrt(n) since, we can claim one of the following:
1) n is a prime number
2) If n has a prime factor p greater than sqrt(n), then there exists a corresponding prime factor p’ lesser than or equal to sqrt(n), such that
p*p’ = n
If (1) doesn’t hold, it implies that n is a composite number. And Let us assume (2) doesnt hold.
This implies for a prime p such that p|n, there is no p’ <= sqrt(n) such that p’|n.
In particular n/p > sqrt(n) . And since p>sqrt(n)
=> 1/p < 1/sqrt(n)
=> n/p <n/sqrt(n) = sqrt(n).
This provides the contradiction. Hence the claim above proves the correctness of the algorithm.
Link to a JAVA implementation of the above factorization.