Recently, I am teaching students algorithm using Python. One question is to find maximum prime factor of a given number. When we consider algorithm, we should consider both the running time and occupied memory of the program when the input is an extremely big number.

The following algorithm is very typical to get the prime factor of any given number. You could find out the code everywhere on the Internet. In this post, I will explain why it is written like this and what are the key questions behind its concise implementation. So let’s start now!

At line 5, the input parameter n represents any positive integer. It starts searching the prime factors from the smallest prime number, 2. The code from line 7 to line 9 loops until all the prime factor 2 is found out. Remember to divide number n by its prime factor 2 in each iteration.

From line 11 to line 14, The program searches all the possible prime factors starting from 3. Since 2 is the only even prime factor, the program could skip all the other even numbers and just search the odd numbers. This operation reduces the running time by 50%.

From line 11 to line 17, the seven lines contain at least two confusion points.

Question 1:

One typical question for the line 11 to 14 is: if we traverse all the odd numbers, how about we pick up those non-prime odd numbers?

I would say it is not possible. Notice that if the odd number is not a prime number, its own prime factors have already been searched out (since the loop iterates in ascending order). Since the number n is divided by its prime factor each time, when non-prime number divides the number n, it is not possible to return True for expression “i % n == 0”. Therefore, it is not possible to pick up the non-prime number as prime factor.

Second question:

Another question for the loop is the stopping condition. Notice that the loop finishes when it iterates to int(sqrt(n)) + 1. Is it enough to traverse to int(sqrt(N)) + 1? How about there are bigger prime factors than the number int(sqrt(N)) + 1?

Let’s assume all the prime factors of a number n are:

F₁, F₂, F₃, F₄ and F₅ (in ascending order)

N could be represented as N = F₁ x F₂ x F₂ x F₃ x F₃ x F₄ x F₅

Condition #1: If F₁ x F₂ x F₂ x F₃ x F₃ x F₄ < F₅, then F₅ is the only number bigger than sqrt(N).

e.g. 414 = 2 x 3 x 3 x 23,

2 x 3 x 3 < 23, then the biggest prime factor 23 is bigger than int(sqrt(414)) = 21.

Condition #2: If F₁ x F₂ x F₂ x F₃ x F₃ x F₄ > F₅, then when searching to sqrt(N), all the factors have been searched out because F₅ is smaller than sqrt (N).

e.g. 126 = 2 x 3 x 3 x 7,

2 x 3 x 3 > 7, then the biggest prime factor 7 is smaller than int(sqrt(126)) = 11.

Here, F₅ is not possible to be equal to F₁ x F₂ x F₂ x F₃ x F₃ x F₄ since that means F₅ is not a prime number.

Once we search till sqrt (n), it is possible that all the prime factors have been searched out (Condition #2), or we only have one prime factor left which is bigger than sqrt(n) (Condition #1).

Since number n’s value changes every time (line 14, n = n // i) the program finds a prime factor. At line 16, the value of number n is equal to the quotient of original number n divided by all the found prime factors. At this point, the program just need to judge if the number n is still bigger than 1. if it is, the program hits condition #1, and the number n represents the maximum prime factor. If the number n is equal to 1, the program hits condition #2, so we do not need to do anything. the value of max_Prime represents the maximum prime number.

Through traversing to int(sqrt(N)) + 1 instead to N, the running time of the program decreases exponentially.

That is all about the implementation of the function. The following code is used to run the function and record its performance. I will not explain them in this post.

Using the above algorithm to get the biggest prime factor of a super big number, it is pretty efficient, as shown in the below image.

That is all for this post. Enjoy the coding and have fun!

Note: All the analysis articles are copyright products of http://www.thecodingfun.com. Anyone re-posting them should credit author and original source. Anyone using them for commercial purposes or translating them into other languages should notify TheCodingFun and get confirmation first. All Rights Reserved.