Find and print the factors of the number in Python

Learn how to find the factors of a number in Python with this simple program.

Finding the factors of the number in Python

There are several ways to find and print the factors of the number, first being to iterate through every number up to ‘N’ and check by dividing it whether it is divisible by it or not. This is a naive approach and takes a lot of time for very large values of ‘N’. The efficient and a better approach is to iterate through the square of the number ‘N'(inclusive) if ‘N’ is not even i.e. odd else exclusive(you will know shortly). This approach reduces the complexity of O(n) to O(√n). Let’s begin with finding the factors of a number N in Python3.

Find the factors of a number in Python

First, let’s try using the naive approach:

N=int(input()) 
factors=[1] 
for i in range(2,N):
   if(N%i==0): 
      factors.append(i) 
factors.append(N) 
print(factors)
Output:
24
[1, 2, 3, 4, 6, 8, 12, 24]

Time Complexity=O(n)

Efficient approach:

An efficient approach for finding the factors of the number N. Check whether the number is a perfect square or not and instead of iterating from 1 to N iterate up to the square root(N). The idea is to find the modulus of N and check whether it is evenly divisible or it, if yes include the divisor in factor’s list as well as the quotient to factor’s list. The problem arises if the number appears to be a perfect square we will get duplicates at this point using the same approach, eg: take N=36 now for 6 it is evenly divisible so it will add the quotient 6 also and there will be two 6’s and we don’t want this hence we don’t include the square root(N) in iteration. Note the below two points:

  • If N is not a perfect square iterate through the square root(N)+1.
  • If not iterate through the square root(N)

We can also use set to store the factors but then there would be +1 more iteration than using list hence I suggest using this approach.

The python 3 implementations for the above approach is given below, but I would recommend you all to try this on your own and then see the code as assistance if you get stuck.

from math import sqrt
N=int(input())
temp1=sqrt(N)
temp2=int(temp1)
factors=[1,N]
if(temp1==temp2):
    for i in range (2,temp2):
        if(N%i==0):
            factors.append(i)
            factors.append(N//i)
    factors.append(temp2)
else:
    for i in range (2,temp2+1):
        if(N%i==0):
            factors.append(i)
            factors.append(N//i)
print(factors)
Output: 
24 
[1, 2, 3, 4, 6, 8, 12, 24]

Time Complexity=O(√n)

Also learn: Mathematical Functions in Python

Leave a Reply

Your email address will not be published. Required fields are marked *