Kodeclik Blog
Python program to print all prime factors of a given number
In mathematics, factorization or factoring is the decomposition of a number into a product of other numbers. Prime factorization, in particular, means that we are decomposing the number into prime numbers (like 2,3,5). For instance, given 24, the prime factorization is: 24 = 2x2x2x3. In other words, the prime factorization of 24 contains three 2s and one 3.
We will cover two general approaches to print all prime factors of a given number. We will learn each of these methods next.
Method 1: Brute-force search
Our first method for factorization works as follows. Note that we can always reorder the prime factors from small to large, so we can first see how many 2s could be in the prime factorization, followed by how many 3s and so on. Here is how that program looks:
def find_prime_factors(n):
factorlist = []
factor = 2
while (n>1):
if (n % factor == 0):
factorlist.append(factor)
n = n/factor
else:
factor = factor +1
return(factorlist)We first define a function called “find_prime_factors” that takes a number (n) as input. We begin by checking if 2 is a factor. If 2 is a factor, we append it to the “factorlist” (which is empty to start with). Then we halve the number (because 2 is a factor) and see if that halved number has a 2 as a factor. If not, we can conclude that the number is not even and thus we should move on to considering the next factor, i.e., 3. This is what is happening in the “else” clause of the if condition. These steps are continually repeated (in the while loop) while the number is greater than 1.
Let us try finding the prime factors of 30. We do:
print(find_prime_factors(30))We will get:
[2, 3, 5]If we try a number that has a repeated prime factor, e.g., 4, we will try:
print(find_prime_factors(4))and the answer is:
[2, 2]Now you might wonder - how does this program give me prime factors when I am not really checking for primes anywhere in the code? The reason is subtle. 2 is the first prime number tested in the code. Following the factoring of 2s out of the number, we check for the presence of 3s in the factorization. After this, the code will move onto checking for the presence of 4s. But you can be sure that, because 4 is a composite number, its factors (namely 2) would have been tested earlier and would have been identified earlier. As a result the inner if condition will fail whenever “factor” is a composite number. We will of course be doing a lot of checks that will turn out to be useless (in the if condition) but the correctness of the program is not affected.
Method 2: Smarter search
The smarter search algorithm is a simple modification to the earlier one. First we try to see how many times we can factor 2 out of the given number. Once we cannot factor any more 2s, we can conclude that the number remaining must be an odd number and therefore we need only try odd factors. Further, once the number is fully factored, we exit the search for more factors. The program looks like this:
import math
def find_prime_factors(n):
factorlist = []
num = n
while (n % 2 == 0):
factorlist.append(2)
n = n/2
for i in range(3,int(num/2)+1,2):
while (n % i == 0):
factorlist.append(i)
n = n/i
if (n==1):
break
return(factorlist)If we try:
print(find_prime_factors(30))We will get the same answer as before:
[2, 3, 5]Let us now take our program out for a spin by trying it out on different numbers and observing it in action.
For this purpose, we will add a few print statements as we are finding the factors:
import math
def find_prime_factors(n):
factorlist = []
num = n
while (n % 2 == 0):
factorlist.append(2)
n = n/2
print(int(n*2),"=",2,"x",int(n))
for i in range(3,int(num/2)+1,2):
while (n % i == 0):
factorlist.append(i)
n = n/i
print(int(n*i),"=",i,"x",int(n))
if (n==1):
break
return(factorlist)Prime factorization of 24
To find the prime factorization of 24, we do:
print(find_prime_factors(24))The output is:
24 = 2 x 12
12 = 2 x 6
6 = 2 x 3
3 = 3 x 1
[2, 2, 2, 3]So we find the factor 2 three times, and then find 3 as a factor. The number remaining is one and thus the program exits and the factorization is complete.
Prime factorization of 36
Let us do the prime factorization of 36:
print(find_prime_factors(36))The answer is:
36 = 2 x 18
18 = 2 x 9
9 = 3 x 3
3 = 3 x 1
[2, 2, 3, 3]We find two 2’s and two 3’s to make the factorization of 2 squared times 3 squared equals 36.
What are the prime factors of 40?
The prime factorization of 40 is computed by:
print(find_prime_factors(40))The output is:
40 = 2 x 20
20 = 2 x 10
10 = 2 x 5
5 = 5 x 1
[2, 2, 2, 5]Because 40 is 8 times 5 and 8 is 2 cubed, we find four factors as shown above.
Prime factorization of 56
The prime factorization of 56 is computed by:
print(find_prime_factors(56))The output is:
56 = 2 x 28
28 = 2 x 14
14 = 2 x 7
7 = 7 x 1
[2, 2, 2, 7]This number is similar to the earlier one in that it has three 2’s in it. In place of the 5, we have a 7 and the factorization is complete.
Factors of 63
This is our first instance of a number that is not even. The prime factorization can be computed by:
63 = 3 x 21
21 = 3 x 7
7 = 7 x 1
[3, 3, 7]Note that the program begins to find factors only at the 3 level. After two 3s, we find one 7 and we are done.
Prime factorization of 99
This is similar to the earlier one in that the number is not even. Let us try:
print(find_prime_factors(99))The output is:
99 = 3 x 33
33 = 3 x 11
11 = 11 x 1
[3, 3, 11]Prime factorization of 120
Let us try a large number:
print(find_prime_factors(120))We get:
120 = 2 x 60
60 = 2 x 30
30 = 2 x 15
15 = 3 x 5
5 = 5 x 1
[2, 2, 2, 3, 5]Square root of 121
For a number like 121 which is a prime squared, we get the factorization as follows:
print(find_prime_factors(121))with output:
121 = 11 x 11
11 = 11 x 1
[11, 11]Such numbers, i.e., prime squared, are numbers with exactly three factors: 1, the number itself, and the square root of the number. (Recall that prime numbers have two factors, 1 and the number itself).
Pollard Rho Method
For really large numbers, the above algorithms can get time consuming. In such cases we turn to probabilistic algorithms which have a small probability of failure but work quite well in practical situations. The Pollard rho method is a probabilistic algorithm that is faster than trial division for large numbers. The idea behind this method is to keep track of two numbers, x and y, that start at 2 (the smallest possible prime number). To generate the next x, we take the previous x value and square it. Then, we take this result and mod it by our number N that we are trying to factor. So far, we have x2 (mod N). Next, we take y and square it and then mod it by N as well. Now we have y2 (mod N). After that, we take x2-y2 (mod N). This gives us a new x value that is closer to our original number N than our previous x was. By doing this over and over again, eventually x and y will be equal to each other which means that their difference will be 0 (mod N) . And if their difference is 0 (mod N), then N must be a divisor of 0 which means that N is not a prime number! We will leave it to you to code this in Python.
If you liked this blogpost, checkout our blogpost on how to find all factors of a given number, i.e., not just prime factors.
Interested in more things Python? Checkout our post on Python queues. Also see our blogpost on Python's enumerate() capability. Also if you like Python+math content, see our blogpost on Magic Squares. Finally, master the Python print function!
Want to learn Python with us? Sign up for 1:1 or small group classes.
