Factors Of A Number In Python

You might have heard about multiples and factors of a number in Python. If you are reading this blog, I can definitely tell you that you are looking to write a program for finding factors of a number. In this article, we will discuss and implement a program to find factors of a number in python.

What Are Factors Of A Number?

A number N is said to be the factor of another number M if N completely divides M. In other words, If we are given two numbers N and M and Upon dividing M by N, there is no remainder then N is called a factor of M. You can also easily identify that any factor of a number is always less than or equal to the number itself.

For instance, 5 is a factor of 20 as 20 divided by 5 gives 4 as output with no remainder. 

How To Find Factors Of A Number In Python?

To find the factors of a number M, we can divide M by numbers from 1 to M. While dividing M, if a number N leaves no remainder, we will say that N is a factor of M. For this purpose, we can use a for loop in python as follows.

factors = set()
M = 120  # number whose factors we need to find
for N in range(1, M + 1):
    if M % N == 0:  # remainder is zero
        factors.add(N)
print("Factors of {} are {}".format(M, factors))

Output:

Factors of 120 are {1, 2, 3, 4, 5, 6, 8, 40, 10, 12, 120, 15, 20, 24, 60, 30}

In the above example, we have declared a set named factors to store the factors of the number M. If any number leaves remainder 0 when it divides M, we add the number to the set. After the execution of the for loop, we get a set of all the factors of the number M.

As we know, the only factor of a number M greater than M/2 is M itself. So, we can skip dividing M by numbers greater than M/2 to find the factors of M more efficiently as follows.

factors = set()
M = 120  # number whose factors we need to find
factors.add(M)  # a number is a factor of itself
for N in range(1, M // 2 + 1):
    if M % N == 0:  # remainder is zero
        factors.add(N)
print("Factors of {} are {}".format(M, factors))

Output:

Factors of 120 are {1, 2, 3, 4, 5, 6, 8, 40, 10, 12, 15, 20, 120, 24, 60, 30}

We know that factors of a number occur in pairs. For example, factors of a number M can be present in the pairs (1, M), (2, M/2), (3, M/3), (4, M/4) till (M1/2, M^1/2). So, instead of using a for loop to check for factors till M/2, we will check for factors till M^1/2. Whenever we find a factor, we will also store its pair in the set containing all the factors. In this way, we can find factors of a number in python more efficiently.

factors = set()
M = 120  # number whose factors we need to find
factors.add(M)  # a number is a factor of itself
for N in range(1, M):
    if N * N > M:
        break
    if M % N == 0:  # remainder is zero
        factors.add(N)
        factors.add(M // N)
print("Factors of {} are {}".format(M, factors))

Output:

Factors of 120 are {1, 2, 3, 4, 5, 6, 40, 8, 10, 12, 15, 20, 120, 24, 60, 30}

Conclusion

In this article, we have discussed three programs to find factors of a number in python. To learn more about numbers in python, you can read this article on decimal numbers in python. You might also like this article on complex numbers in python.