Oleksii Trekhleb | Javascript algorithms (Prime factors)
This is a series of books diving deep into the core mechanisms of the JavaScript language.
· 2 phút đọc.
Prime number is a whole number greater than 1 that cannot be made by multiplying other whole numbers. The first few prime numbers are: 2, 3, 5, 7, 11, 13, 17, 19 and so on.
If we can make it by multiplying other whole numbers it is a Composite Number.
Image source: Math is Fun
Prime factors are those prime numbers which multiply together to give the original number. For example 39 will have prime factors of 3 and 13 which are also prime numbers. Another example is 15 whose prime factors are 3 and 5.
Image source: Math is Fun
Finding the prime factors and their count accurately
The approach is to keep on dividing the natural number n by indexes from i = 2 to i = n (by prime indexes only). The value of n is being overridden by (n / i) on each iteration.
The time complexity till now is O(n) in the worst case scenario since the loop runs from index i = 2 to i = n. This time complexity can be reduced from O(n) to O(sqrt(n)). The optimisation is achievable when loop runs from i = 2 to i = sqrt(n). Now, we go only till O(sqrt(n)) because when i becomes greater than sqrt(n), we have the confirmation that there is no index i left which can divide n completely other than n itself.
Hardy-Ramanujan formula for approximate calculation of prime-factor count
In 1917, a theorem was formulated by G.H Hardy and Srinivasa Ramanujan which states that the normal order of the number ω(n) of distinct prime factors of a number n is log(log(n)).
Roughly speaking, this means that most numbers have about this number of distinct prime factors.
