Factors Of A Number In Python

0
33 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
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
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, M1/2). So, instead of using a for loop to check for factors till M/2, we will check for factors till M1/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
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}