Skip to content

Latest commit

 

History

History
37 lines (21 loc) · 2.42 KB

File metadata and controls

37 lines (21 loc) · 2.42 KB

Prime Factors

Read this in other languages: 简体中文.

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.

Composite numbers

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.

Factors

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.

References