Kodeclik Blog
Find all factors of a number in Python
Recall that factorization is the process of breaking down an integer into its component parts. For example, if you have the number 24, it can be broken down into 2 * 3 * 4 = 24. The individual numbers that make up the product (2, 3, and 4) are called factors and they make up the factorization of 24.
Now that we understand what factorization is and why it’s important, let’s look at how to do it in Python. There are broadly two ways to do so. First, we can systematically test numbers from 1 sequentially to see if they are factors of the given number. Second, we can use the property that factors will occur in pairs and find pairs till the square root of the given number. We will explore both approaches next!
Method 1: Sequentially test numbers from 1 to the given number
The most straightforward way to do this is by using a looping structure such as a for loop or a while loop. This allows us to systematically test each possible factor from 1 up until the given number itself. For example, if we wanted to find all the factors for 12, we would start with 1 and work our way up until 12 . At each step, we check if our current number divides evenly into 12 . If it does, then we add it to our list of factors . Once we reach 12, we stop because any further numbers would not meet our criteria of dividing evenly into 12 . Here is what this code would look like in Python:
def find_factors(n):
factorlist = []
for i in range(1,n+1):
if (n%i == 0):
factorlist.append(i)
return(factorlist)Note that the range function begins with 1 (not the default zero) and goes on till n, the given input number. This is why the second argument of range() is n+1 which is one more than the end of the loop. At each step we test if the given number is a factor and if so we add it to the “factorlist”. If we run this program like so:
print(find_factors(48))
print(find_factors(72))we will obtain:
[1, 2, 3, 4, 6, 8, 12, 16, 24, 48]
[1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72]This is obviously not a very “Python-ic” way to write programs. Here is the more concise version using a list comprehension:
def find_factors(n):
return [i for i in range(1,n+1) if (n%i == 0)]
print(find_factors(48))
print(find_factors(72))Note that the program logic is the same. We have just found a way to write it succinctly. The output will be the same as before:
[1, 2, 3, 4, 6, 8, 12, 16, 24, 48]
[1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72]Method 2: Find factors of a given number in pairs
In the second method we will explore we will be a bit more organized. We will exploit the fact that factors always come in pairs. For instance, in the case of 48, the pairs are (1,48), (2,24), (3,16), (4,12), and (6,8). Note that each pair multiplies to 48 and further we can pick these pairs by simply picking numbers from the opposite ends of the output we received from method 1. For instance, the first factor we find for 48 is 1, the last factor is 48, so the pair is (1,48). Similarly, the second and second-to-last factors give us (2,24).
Here is an old style Python program to accomplish this task:
def find_factors(n):
factorlist = []
for i in range(1,int(n**0.5)+1):
if (n%i == 0):
factorlist.append(i)
f = int(n/i)
if (f != i):
factorlist.append(f)
return(factorlist)There are some key differences between this and the previous program. First, note that in the range() function we only go from 1 to the square root of the given number (plus 1 is added because the second argument of the range function is not inclusive). Second, we append two numbers (the pair) after each testing: the factor (i) and the divisor when using this factor (n/i, which is stored in variable f). But we have to be careful when the factor is a square root, and so we should avoid adding this factor twice. This is why we have the second if condition inside the first if condition.
When we run this program on our two example numbers above (48 and 72):
print(find_factors(48))
print(find_factors(72))we get:
[1, 48, 2, 24, 3, 16, 4, 12, 6, 8]
[1, 72, 2, 36, 3, 24, 4, 18, 6, 12, 8, 9]Note how the numbers are not arranged sequentially like before. Instead you have to read them in pairs: (1,72), (2,36), (3,24), (4,18), (6,12), (8,9). To confirm that this works, we can try using it with square numbers, like so:
print(find_factors(49))
print(find_factors(64))The output is:
[1, 49, 7]
[1, 64, 2, 32, 4, 16, 8]Note that both of them yield an odd number of factors because the last number added is the square root of the given number. Thus, the factors of 49 are (1,49) and 7. Similarly, the factors of 64 are (1,64), (2,32), (4,16), and 8.
Finally, again we can try to write this program in a more Python-ic style, i.e., using list comprehensions. The easiest way to do this is to make the comprehension generate pairs and then we post-process the pairs to remove the duplicate square root addend as a factor.
from itertools import chain
def find_factors(n):
x = list(chain.from_iterable((i,int(n/i))
for i in range(1,int(n**0.5)+1) if n%i == 0))
if (x[-1] == x[-2]):
return(x[0:-1])
else:
return(x)Note that for each iteration in the list comprehension we add two elements as a tuple. These tuple elements are unpacked and added as single elements using the chain iterator from the itertools package. That is then converted into a list. Finally, we check for the case where two factors are the same (this will happen only with the last two elements): if so we use only one of them. When we run this program using the same inputs as above:
print(find_factors(49))
print(find_factors(64))we will get the same outputs:
[1, 49, 7]
[1, 64, 2, 32, 4, 16, 8]Finding factors of numbers can be useful for many programming applications including cryptography and data analysis. Fortunately, finding these factors with Python doesn't require much effort thanks to the two methods we have seen above. The first approach is simpler but does more testing. If you have a really large number (imagine a billion etc) you will be performing a lot of useless checks because the highest factor is the square root of the number. The second approach is thus more computationally efficient but a bit more complicated. Which one is your favorite approach?
If you liked this blogpost, checkout our blogpost on how to find the prime factorization of a given number.
For more Python content, checkout the math.ceil() and math.floor() functions! Also
learn about the math domain error in Python and how to fix it!
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.
