Algorithm Interview

Finding Prime Factors of an Integer in Python

A frequently-asked question in tech interviews

As we all know, an integer can be decomposed into the multiplication of several prime factors.

But how to print a number’s prime factors in Python? Effectively and efficiently?

This is a classic interview question for junior Python developers.

The interview question

Please write a Python function, the input is an integer and the output is a list of its prime factors.

Analysis

Intuitively, if you can have a big table for all prime numbers. This problem is super easy. You just need to try them one by one and collect the prime numbers that can divide the input number.

However, you cannot ask the interviewer to give you a prime table. 😄

But luckily, we don’t really need this big table. In mathematics, there is a method called the sieve of Eratosthenes.

The idea of using the sieve method to find prime numbers is to arrange a group of positive integers from 2 to N in order from small to large. Delete multiples of 2, multiples of 3, and multiples of 5 in turn, until the multiples of the square root of N, and the rest are all prime numbers between 2 and N.

This idea can solve our prime factorization problem as well.

The implementation

Talk is cheap, let’s see the code:

The above code brings the idea of the sieve of Eratosthenes. It checks the divisibility from 2, which is the first prime number, to the square root of the input number. All numbers that can divide num will be added to the factors list. Finally, if the num is still larger than 1, it means the final num itself is a prime number and it needs to be added as well.

Thanks for reading. Join Medium through my referral link to access millions of great articles:

Further reading: