In this article we will discuss three methods to Find All the Factors of a given Number. The codes provided will be in Python, but same logic can be used to implement in any other language as well.
Table of Contents
Iterative Program to Find All Factors of a Number
This method uses modulus operation(%) to Find All the Factors of a given Number, using a FOR loop to iterate over the number. Below is the simple Python implementation-
#Iterative Solution to Find All the Factors of a Number
def factor(n):
print("The Factors of "+str(n)+" are: ",end="")
for i in range(1,n+1):
if(n%i==0):
print(i,end=" ")
factor(4)
Dry Run
- Let’s take n = 4
- In the first iteration i = 1, since 4 leaves a remainder of zero when divided by 1, 1 is printed.
- In the second iteration i = 2, since 4 leaves a remainder of zero when divided by 2, 2 is printed.
- In the third iteration i = 3, since 4 leaves a remainder of one when divided by 3, 3 is not printed.
- In the fourth iteration i = 4, since 4 leaves a remainder of zero when divided by 4, 4 is printed.
- The loop breaks when i attains the value 5.
Time Complexity: Theta(value of the number) = Theta(n)
Space Complexity = Auxiliary Space = Theta(1)
Optimized Solution to Find All Factors of a Number
The idea of the optimized solution is that factors occur in pair. For example if n = 50, then the various pairs of divisors are: (1, 50), (2, 25),(5, 10).
Using this fact we could speed up our program significantly.
We, however, have to be careful if there are two equal divisors as in the case of (10, 10). In such case, we’d print only one of them.
Below is an implementation for the same:
#Optimized Solution to Find All the Factors of a Number
import math
def factor(n):
i=1
while(i <= math.sqrt(n)):
if(n%i == 0):
# If divisors are equal, print only one
if (n / i == i) :
print(i,end=" ")
else :
# Otherwise print both
print(i , n//i,end =" ")
i += 1
print("The divisors of 4 are: ")
factor(4)
Output:
The divisors of 4 are:
1 4 2
Time Complexity: Theta(value of the number) = Theta(sqrt(n))
Space Complexity = Auxiliary Space = Theta(1)
Dry Run:
- In the first iteration i = 1, since 4 leaves a remainder of zero when divided by 1 and 4 divided by 1 is not equal to one therefore, 1 and 4 both are printed.
- In the second iteration i = 2, since 4 leaves a remainder of zero when divided by 2 and 4 divided by 2 is equal to two therefore, only 2 is printed.
- The loop breaks when i attains the value 3.
Explanation for the Optimized Solution
The factors of any Number ‘N’ occur in pairs. Suppose N =15 , in this case the factors are 1, 3, 5, 15 and the pairs are (1, 15) , (3, 5). So, if we find one factor in a pair, we can easily find the other factor by dividing the number with that factor. Example: 3 is a factor of 15 and upon division of 15 by 3, we get 5 as a Quotient, which is also another factor of 15.
So, we use a loop to iterate over the values lesser than the square root of n, and using these values we find the ones which are factors of N. Using these factors, we perform the division of N and use the quotient,which is in fact a factor of N having a value greater than square root of N.
In the second optimized solution, we use another loop (In this case, a FOR loop) to print the factors in a sorted manner.
Optimized Solution to Find All Factors of a Number (Sorted order)
In the previous solution, the sequence in which the factors of the number was not printed in the correct order. This solution corrects that.
#Optimized Solution to Find All the Factors of a Number (Sorted)
import math
def factor(n):
i=1
while(i <= math.sqrt(n)):
if(n%i == 0):
print(i,end=" ")
i += 1
i=int(math.sqrt(n))
for t in range(i, 0, -1):
if(n % t == 0) and (n/t != t):
print(n//t,end=" ")
print("The divisors of 4 are: ")
factor(4)
Output:
The divisors of 4 are:
1 2 4
Time Complexity: Theta(value of the number) = Theta(sqrt(n))
Space Complexity = Auxiliary Space = Theta(1)