Read this in other languages: Giản thể tiếng Trung.
Prime numberis a whole number greater than1thatcannotbe made by multiplying other whole numbers. The first few prime numbers are:2,3,5,7,11,13,17,19and so on.
If wecanmake it by multiplying other whole numbers it is aComposite Number.
Image source:Math is Fun
Prime factorsare thoseprime numberswhich multiply together to give the original number. For example39will have prime factors of3and13which are also prime numbers. Another example is15whose prime factors are3and5.
Image source:Math is Fun
The approach is to keep on dividing the natural numbernby indexes fromi = 2toi = n(by prime indexes only). The value ofnis being overridden by(n / i)on each iteration.
The time complexity till now isO(n)in the worst case scenario since the loop runs from indexi = 2toi = n.This time complexity can be reduced fromO(n)toO(sqrt(n)).The optimisation is achievable when loop runs fromi = 2toi = sqrt(n).Now, we go only tillO(sqrt(n))because whenibecomes greater thansqrt(n),we have the confirmation that there is no indexileft which can dividencompletely other thannitself.
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 numbernislog(log(n)).
Roughly speaking, this means that most numbers have about this number of distinct prime factors.