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.